您好,登錄后才能下訂單哦!
今天小編給大家分享一下C語(yǔ)言單雙線性及循環(huán)鏈表怎么實(shí)現(xiàn)的相關(guān)知識(shí)點(diǎn),內(nèi)容詳細(xì),邏輯清晰,相信大部分人都還太了解這方面的知識(shí),所以分享這篇文章給大家參考一下,希望大家閱讀完這篇文章后有所收獲,下面我們一起來(lái)了解一下吧。
Operation
InitList(*L):初始化操作,簡(jiǎn)歷一個(gè)空的線性表L
ListEmpty(L):判斷線性表是否為空表,若線性表為空返回true,否則返回false
ClearList(*L):將線性表清空
GetElem(L,i,*e):將線性表L中的第i個(gè)位置返回給e
LocatElem(L,e):在線性表L中查找與給定值e相等的元素,如果查找成功,返回該元素在表中序號(hào)表示成功,否則,返回0表示失敗
ListInsert(*L,i,e):在線性表L中第i個(gè)位置插入元素e
ListDelete(*L,i,*e):刪除線性表L中的第i個(gè)位置的元素,并用e返回其值
ListLength(L):返回線性表L的元素個(gè)數(shù)
線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素,這組存儲(chǔ)單元可以存在內(nèi)存中未被占用的任意位置。
比起順序存儲(chǔ)結(jié)構(gòu)每個(gè)數(shù)據(jù)元素只需要存儲(chǔ)一個(gè)位置就可以了。
現(xiàn)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中,除了要存儲(chǔ)數(shù)據(jù)元素信息外,還要存儲(chǔ)它的后繼元素的存儲(chǔ)地址(指針)
我們把存儲(chǔ)數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域,把存儲(chǔ)直接后繼位置的域稱為指針域。指針域中存儲(chǔ)的信息稱為指針或鏈。這兩部分信息組成數(shù)據(jù)元素稱為存儲(chǔ)映像,稱為結(jié)點(diǎn)(Node)。
n個(gè)結(jié)點(diǎn)鏈接成一個(gè)鏈表,即為線性表(a1,a2,a3, …., an)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。
因?yàn)榇随湵淼拿總€(gè)結(jié)點(diǎn)中只包含一個(gè)指針域,所以叫做單鏈表。
獲得鏈表第i個(gè)數(shù)據(jù)的算法思路:
聲明一個(gè)結(jié)點(diǎn)p指向鏈表第一個(gè)結(jié)點(diǎn),初始化從1開(kāi)始
當(dāng)j<i時(shí),就遍歷鏈表,讓p的指針向后移動(dòng),不斷指向一下結(jié)點(diǎn),j+1;
若到鏈表末尾p為空,則說(shuō)明第i個(gè)元素不存在;
否則查找成功,返回結(jié)點(diǎn)p的數(shù)據(jù)。
通俗易懂就是從頭開(kāi)始找,直到第i個(gè)元素為止。
由于這個(gè)算法的時(shí)間復(fù)雜度取決于i的位置,當(dāng)i=1時(shí),則不需要遍歷,而i=n時(shí)則遍歷n-1次才可以。因此最壞情況的時(shí)間復(fù)雜度為O(n)。
由于單鏈表的結(jié)構(gòu)中沒(méi)有定義表長(zhǎng),所以不能實(shí)現(xiàn)知道要循環(huán)多少次,因此也就不方便使用for控制循環(huán)。
其核心思想叫做“工作指針后移”,這其實(shí)也是很多算法的常用技術(shù)。
看圖發(fā)現(xiàn)我們插入結(jié)點(diǎn)不需要向順序存儲(chǔ)一樣全部更改,只需要讓s -> next和p -> next發(fā)生一點(diǎn)指向改變:
s -> next = p-> next
p -> next = s
如圖:
單鏈表第i個(gè)數(shù)據(jù)插入結(jié)點(diǎn)的算法思路:
1.聲明一結(jié)點(diǎn)p指向鏈表頭結(jié)點(diǎn),初始化j從1開(kāi)始;-當(dāng)j<i時(shí),就遍歷鏈表,讓p的指針向后移動(dòng),不斷指向下一結(jié)點(diǎn),j累加1;
2.若到鏈表末尾p為空,則說(shuō)明第i個(gè)元素不存在;
3.否則查找成功,在系統(tǒng)中生成一個(gè)空結(jié)點(diǎn)S;
4.將數(shù)據(jù)元素e賦值給s->data;
5.單鏈表的插入剛才兩個(gè)標(biāo)準(zhǔn)語(yǔ)句;
6.返回成功
(表示類型)malloc(sizeof(表示長(zhǎng)度))開(kāi)辟一個(gè)空間
假設(shè)元素a2的結(jié)點(diǎn)為q,要實(shí)現(xiàn)結(jié)點(diǎn)q刪除單鏈表的操作,其實(shí)就是將它的前繼結(jié)點(diǎn)的指針繞過(guò)指向后面。我們要做的就是上一步
可以寫(xiě)成 p -> next = p ->next -> next
也可以使用
q = p -> next;p -> next = q -> next
單鏈表第i個(gè)數(shù)據(jù)刪除結(jié)點(diǎn)的算法思路:
聲明結(jié)點(diǎn)p指向鏈表第一個(gè)結(jié)點(diǎn),初始化j=1;
當(dāng)j < i時(shí),就遍歷鏈表,讓P的指針向后移動(dòng),不斷指向下一個(gè)結(jié)點(diǎn),j累加1;
一若到鏈表末尾p為空,則說(shuō)明第i個(gè)元素不存在;
否則查找成功,將欲刪除結(jié)點(diǎn)p->next賦值給q;
單鏈表的刪除標(biāo)準(zhǔn)語(yǔ)句p -> next = q -> next ;
將q結(jié)點(diǎn)中的數(shù)據(jù)賦值給e,作為返回;
釋放q結(jié)點(diǎn)。free(q)
創(chuàng)建單鏈表的過(guò)程是一個(gè)動(dòng)態(tài)生成鏈表的過(guò)程,從“空表“的初始狀態(tài)起,依次建立各元素結(jié)點(diǎn)并逐個(gè)插入鏈表。
所以單鏈表整表創(chuàng)建的算法思路如下:
聲明一結(jié)點(diǎn)p和計(jì)數(shù)器變量i;
初始化一空鏈表L;
讓L的頭結(jié)點(diǎn)的指針指向NULL,即建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表;
循環(huán)實(shí)現(xiàn)后繼結(jié)點(diǎn)的賦值和插入。
頭插法從一個(gè)空表開(kāi)始,生成新結(jié)點(diǎn),讀取數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中,然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上,直到結(jié)束為止。
簡(jiǎn)單來(lái)說(shuō),就是把新加進(jìn)的元素放在表頭后的第個(gè)位置:
先讓新節(jié)點(diǎn)的next指向頭節(jié)點(diǎn)之后
然后讓表頭的next指向新節(jié)點(diǎn)
嗯,用現(xiàn)實(shí)環(huán)境模擬的話就是插隊(duì)的方法,始終讓新結(jié)點(diǎn)插在第一的位置。
聲明結(jié)點(diǎn)p和q;
將第一個(gè)結(jié)點(diǎn)賦值給p,下一結(jié)點(diǎn)賦值給q;
循環(huán)執(zhí)行釋放p和將q賦值給p的操作;
#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status; Status ClearList(LinkList *L){ LinKList p,q; p = (*L) -> next; while(p){ q = p -> next; free(p); p = q; } (*L) -> next = NULL; return OK } //這段算法代碼里,常見(jiàn)的錯(cuò)誤就是有同學(xué)會(huì)覺(jué)得q變量沒(méi)有存在的必要,只需要在循環(huán)體內(nèi)直接寫(xiě)自由(P);p=p->下一步;即可? //可這個(gè)世上沒(méi)有無(wú)緣無(wú)故的愛(ài),這樣做會(huì)帶來(lái)什么問(wèn)題呢? //要知道p是一個(gè)結(jié)點(diǎn),它除了有數(shù)據(jù)域,還有指針域.當(dāng)我們做自由(P);時(shí)候,其實(shí)是對(duì)它整個(gè)結(jié)點(diǎn)進(jìn)行刪除和內(nèi)存釋放的工作.而我們整表刪除是需要一個(gè)個(gè)結(jié)點(diǎn)刪除的,所以我們就需要q來(lái)記載p的下一個(gè)結(jié)點(diǎn).
#include <stdio.h> #include <stdlib.h> struct singleList{ int data; struct singleList *next; }; //創(chuàng)建一個(gè)表 struct singleList*createList(){ //指針變成結(jié)構(gòu)體變量 struct singleList *headNode = (struct singleList *)malloc(sizeof(struct singleList)); headNode -> next = NULL; //差異化處理,充當(dāng)表頭 return headNode; } //創(chuàng)建結(jié)點(diǎn): 戰(zhàn)門(mén)創(chuàng)建新的結(jié)點(diǎn) //int data struct singleList* creatNode(int data) { struct singleList* newNode = (struct singleList *)malloc(sizeof(struct singleList)); newNode -> data = data; newNode -> next = NULL; return newNode; } void insertNodeByHead(struct singleList *headNoed,int data){ struct singleList *newNode = creatNode(data); newNode -> next = headNoed -> next; headNoed -> next = newNode; } void printList(struct singleList* headNode){ //因?yàn)榈谝粋€(gè)結(jié)點(diǎn)就是表頭,所以 里面沒(méi)有數(shù)據(jù),要從第二個(gè)打印 struct singleList *pMove = headNode -> next; while (pMove) { printf("%d -> ",pMove -> data); pMove = pMove -> next; } printf("\n"); } int main(){ struct singleList*list =createList(); insertNodeByHead(list,1); insertNodeByHead(list,2); insertNodeByHead(list,3); printList(list); system("pause"); return 0; }
此處使用c++語(yǔ)法,請(qǐng)自行切換
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> struct student { char name[20]; int age; int num; }; struct singleList { // int data; struct student data; struct singleList* next; }; //創(chuàng)建一個(gè)表 struct singleList* createList() { //指針變成結(jié)構(gòu)體變量 struct singleList* headNode = (struct singleList*)malloc(sizeof(struct singleList)); headNode->next = NULL; //差異化處理,充當(dāng)表頭 return headNode; } //創(chuàng)建結(jié)點(diǎn): 戰(zhàn)門(mén)創(chuàng)建新的結(jié)點(diǎn) //int data struct singleList* creatNode(struct student data) { struct singleList* newNode = (struct singleList*)malloc(sizeof(struct singleList)); newNode->data = data; newNode->next = NULL; return newNode; } void insertNodeByHead(struct singleList* headNoed, struct student data) { struct singleList* newNode = creatNode(data); newNode->next = headNoed->next; headNoed->next = newNode; } void printList(struct singleList* headNode) { //因?yàn)榈谝粋€(gè)結(jié)點(diǎn)就是表頭,所以 里面沒(méi)有數(shù)據(jù),要從第二個(gè)打印 struct singleList* pMove = headNode->next; printf("請(qǐng)錄入信息:姓名\t年齡\t編號(hào)\n"); while (pMove) { printf("%s\t%d\t%d\n ", pMove->data.name, pMove->data.age, pMove->data.num); // struct student data // printf("%d -> ",pMove -> data); pMove = pMove->next; } printf("\n"); } //增刪查改 //void saveInfoToFile() //菜單 void printMenu() { printf("---------------------\n"); printf("\t\to.退出信息\n"); printf("\t\t1.錄入信息\n"); printf("\t\t2.顯示信息\n"); printf("---------------------\n"); } //按鍵處理 struct singleList* list = createList(); void keyDown() { int choice = 0; scanf("%d", &choice); struct student tempDate; switch(choice) { case 0: printf("正常退出\n"); system("pause"); break; case 1: printf("請(qǐng)輸入學(xué)生姓名年齡編號(hào)"); scanf("%s %d %d", tempDate.name, &tempDate.age, &tempDate.num); insertNodeByHead(list, tempDate); break; case 2: printList(list); break; }; } int main() { // struct singleList*list =createList(); // insertNodeByHead(list,1); // insertNodeByHead(list,2); // insertNodeByHead(list,3); // printList(list); while (1) { printMenu(); keyDown(); system("pause"); system("cls"); } system("pause"); return 0; }; //1.先寫(xiě)鏈表,先寫(xiě)數(shù)據(jù)結(jié)構(gòu) //2.修改data //3.系統(tǒng)應(yīng)用開(kāi)發(fā)
main.h
#pragma once #include <stdio.h> #include <stdlib.h> //雙向鏈表結(jié)構(gòu)體 typedef struct doubleLink { char data;//記錄節(jié)點(diǎn)所在的行和列 struct doubleLink* pre;//指向前驅(qū)節(jié)點(diǎn)的指針 struct doubleLink* next;//指向后續(xù)節(jié)點(diǎn)的指針 }; //初始化雙鏈表 struct doubleLink* initDoubleLink(); //查詢 struct doubleLink* selectDoubleLink(struct doubleLink* p, int site); //插入 struct doubleLink* insertDoubleLink(struct doubleLink* p, int site, int value); //刪除 struct doubleLink* deleteDoubleLink(struct doubleLink* p, int site); //修改 struct doubleLink* updateDoubleLink(struct doubleLink* p, int site, int value); //打印 void display(doubleLink* head);
main.cpp
#include "main.h" int main() { printf("雙鏈表\n"); struct doubleLink* doubleLink = NULL; display(doubleLink); doubleLink = initDoubleLink(); display(doubleLink); insertDoubleLink(doubleLink, 2, 100); display(doubleLink); deleteDoubleLink(doubleLink, 2); display(doubleLink); updateDoubleLink(doubleLink, 2, 100); display(doubleLink); return 0; }
doubleLink.cpp
#include "main.h" struct doubleLink* initDoubleLink() { doubleLink* headNode = NULL; doubleLink* temp = NULL; headNode = (doubleLink*)malloc(sizeof(doubleLink)); headNode->data = 0; headNode->next = NULL; headNode->pre = NULL; temp = headNode; for (int i = 1; i <= 4; i++) { doubleLink* a = (doubleLink*)malloc(sizeof(doubleLink)); a->data = i; a->next = NULL; a->pre = temp; temp->next = a; temp = temp->next; } return headNode; } struct doubleLink* insertDoubleLink(struct doubleLink* p, int site, int value) { doubleLink* body = NULL; body = p; doubleLink* temp = NULL; temp = (doubleLink*)malloc(sizeof(doubleLink)); temp->data = value; temp->pre = NULL; temp->next = NULL; body = selectDoubleLink(p, site); temp->next = body->next; temp->pre = body; body->next = temp; return p; } struct doubleLink* deleteDoubleLink(struct doubleLink* p, int site) { doubleLink* body = NULL; body = p; body = selectDoubleLink(p, site); body->next = body->next->next; body->next->pre = body; return p; } struct doubleLink* updateDoubleLink(struct doubleLink* p, int site,int value) { doubleLink* body = NULL; body = p; body = selectDoubleLink(p, site); body->next->data = value; return p; } struct doubleLink* selectDoubleLink(struct doubleLink* p, int site) { doubleLink* temp = p; int i; for (i = 1; i < site; i++) { if (temp == NULL) { printf("查詢失敗"); return p; } temp = temp->next; } return temp; } void display(doubleLink* head) { doubleLink* temp = head; while (temp) { if (temp->next == NULL) { printf("%d\n", temp->data); } else { printf("%d->", temp->data); } temp = temp->next; } }
貪吃蛇實(shí)例展示:
1.我們知道,雙向鏈表中各個(gè)節(jié)點(diǎn)的標(biāo)準(zhǔn)構(gòu)成是一個(gè)數(shù)據(jù)域和 2 個(gè)指針域,但對(duì)于實(shí)現(xiàn)貪吃蛇游戲來(lái)說(shuō),由于各個(gè)節(jié)點(diǎn)的位置是隨貪吃蛇的移動(dòng)而變化的,因此鏈表中的各節(jié)點(diǎn)還需要隨時(shí)進(jìn)行定位。
在一個(gè)二維畫(huà)面中,定義一個(gè)節(jié)點(diǎn)的位置,至少需要所在的行號(hào)和列號(hào)這 2 個(gè)數(shù)據(jù)。由此,我們可以得出構(gòu)成貪吃蛇的雙向鏈表中各節(jié)點(diǎn)的構(gòu)成:
//創(chuàng)建表示蛇各個(gè)節(jié)點(diǎn)的結(jié)構(gòu)體 typedef struct SnakeNode { int x, y;//記錄節(jié)點(diǎn)所在的行和列 struct SnakeNode *pre;//指向前驅(qū)節(jié)點(diǎn)的指針 struct SnakeNode *next;//指向后續(xù)節(jié)點(diǎn)的指針 }Node, *pNode;
2.貪吃蛇的移動(dòng),本質(zhì)上就是對(duì)鏈表中各個(gè)節(jié)點(diǎn)的重新定位。換句話說(shuō),除非貪吃蛇吃到食物,否則無(wú)論怎樣移動(dòng),都不會(huì)對(duì)雙向鏈表的整個(gè)結(jié)構(gòu)(節(jié)點(diǎn)數(shù))產(chǎn)生影響,唯一受影響的就只是各個(gè)節(jié)點(diǎn)中 (x,y) 這對(duì)定位數(shù)據(jù)。
由此,我們可以試著設(shè)計(jì)出實(shí)現(xiàn)貪吃蛇移動(dòng)的功能函數(shù),本節(jié)所用的實(shí)現(xiàn)思想分為 2 步:
從蛇尾(雙向鏈表尾節(jié)點(diǎn))開(kāi)始,移動(dòng)向前遍歷,過(guò)程中依次將當(dāng)前節(jié)點(diǎn)的 (x,y) 修改為前驅(qū)節(jié)點(diǎn)的 (x,y),由此可實(shí)現(xiàn)整個(gè)蛇身(除首元節(jié)點(diǎn)外的其它所有節(jié)點(diǎn))的向前移動(dòng);
接收用戶輸入的移動(dòng)指令,根據(jù)用戶指示貪吃蛇向左、向右、向上還是向下移動(dòng),首元節(jié)點(diǎn)中的 (x,y) 分別做 x-1、x+1、y-1 和 y+1 運(yùn)算。
如下所示,move() 函數(shù)就實(shí)現(xiàn)了貪吃蛇的移動(dòng):
//貪吃蛇移動(dòng)的過(guò)程,即鏈表中所有節(jié)點(diǎn)從尾結(jié)點(diǎn)開(kāi)始逐個(gè)向前移動(dòng)一個(gè)位置 bool Move(pNode pHead, char key) { bool game_over = false; pNode pt = pTail; while (pt != pHead) { // 每個(gè)節(jié)點(diǎn)依次向前完成蛇的移動(dòng) pt->x = pt->pre->x; pt->y = pt->pre->y; pt = pt->pre; } switch (key) { case'd': { pHead->x += 1; if (pHead->x >= ROW) game_over = true; break; } case'a': { pHead->x -= 1; if (pHead->x < 0) game_over = true; break; } case's': { pHead->y += 1; if (pHead->y >= COL) game_over = true; break; } case'w': { pHead->y -= 1; if (pHead->y < 0) game_over = true;; break; } } if (SnakeDeath(pHead)) game_over = true; return game_over; }
注意,此段代碼中還調(diào)用了 SnakeDeath() 函數(shù),此函數(shù)用于判斷貪吃蛇移動(dòng)時(shí)是否撞墻、撞自身,如果是則游戲結(jié)束。
3. 當(dāng)貪吃蛇吃到食物時(shí),貪吃蛇需要增加一截,其本質(zhì)也就是雙向鏈表增加一個(gè)節(jié)點(diǎn)。前面章節(jié)中,已經(jīng)詳細(xì)介紹了如何在雙向鏈表中增加一個(gè)節(jié)點(diǎn),因此實(shí)現(xiàn)這個(gè)功能唯一的難點(diǎn)在于:如何為該節(jié)點(diǎn)初始化 (x,y)?
本節(jié)所設(shè)計(jì)的貪吃蛇游戲,針對(duì)此問(wèn)題,提供了最簡(jiǎn)單的解決方案,就是不對(duì)新節(jié)點(diǎn) x 和 y 做初始化。要知道,貪吃蛇是時(shí)刻移動(dòng)的,而在上面的 move() 函數(shù)中,會(huì)時(shí)刻修正貪吃蛇每個(gè)節(jié)點(diǎn)的位置,因此當(dāng)為雙向鏈表添加新節(jié)點(diǎn)后,只要貪吃蛇移動(dòng)一步,新節(jié)點(diǎn)的位置就會(huì)自行更正。
也就是說(shuō),貪吃蛇吃到食物的實(shí)現(xiàn),就僅是給雙向鏈表添加一個(gè)新節(jié)點(diǎn)。如下即為實(shí)現(xiàn)此功能的代碼:
//創(chuàng)建表示食物的結(jié)構(gòu)體,其中只需要記錄其所在的行和列 typedef struct Food { int x; int y; }Food, *pFood; //吃食物,等同于鏈表中新增一個(gè)節(jié)點(diǎn) pNode EatFood(pNode pHead, pFood pFood) { pNode p_add = NULL, pt = NULL; if (pFood->x == pHead->x&&pFood->y == pHead->y) { p_add = (pNode)malloc(sizeof(Node)); score++; pTail->next = p_add; p_add->pre = pTail; p_add->next = NULL; pTail = p_add; // 檢查食物是否出現(xiàn)在蛇身的位置上 do { *pFood = CreateFood(); } while (FoodInSnake(pHead, pFood)); } return pHead; }
其中,F(xiàn)ood 結(jié)構(gòu)體用來(lái)表示食物,其內(nèi)部?jī)H包含能夠定位食物位置的 (x,y) 即可。另外,此段代碼中,還調(diào)用了 FoodeInSnake() 函數(shù),由于食物的位置是隨機(jī)的,因此極有可能會(huì)和貪吃蛇重合,所以此函數(shù)的功能就是:如果重合,就重新生成食物。
FoodInSnake() 函數(shù)的實(shí)現(xiàn)很簡(jiǎn)單,這里不再贅述:
//判斷食物的出現(xiàn)位置是否和蛇身重合 bool FoodInSnake(pNode pHead, pFood pFood) { pNode pt = NULL; for (pt = pHead; pt != NULL; pt = pt->next) { if (pFood->x == pt->x&&pFood->y == pt->y) return true; } return false; }
4.貪吃蛇游戲界面的顯示,最簡(jiǎn)單的制作方法就是:貪吃蛇每移動(dòng)一次,都清除屏幕并重新生成一次。這樣實(shí)現(xiàn)的問(wèn)題在于,如果貪吃蛇的移動(dòng)速度過(guò)快,則整個(gè)界面在渲染的同時(shí),會(huì)摻雜著光標(biāo),并且屏幕界面會(huì)頻繁閃動(dòng)。
因此,在渲染界面時(shí),有必要將光標(biāo)隱藏起來(lái),這需要用到<windows.h>頭文件,實(shí)現(xiàn)代碼如下:
// 隱藏光標(biāo) void gotoxy(int x, int y) { HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE); COORD pos; pos.X = x; pos.Y = y; SetConsoleCursorPosition(handle, pos); } void HideCursor() { CONSOLE_CURSOR_INFO cursor_info = { 1, 0 }; SetConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE), &cursor_info); }
同時(shí),為了給整個(gè)界面渲染上顏色,也需要引入<windows.h>頭文件,并使用如下函數(shù):
void color(int m) { HANDLE consolehend; consolehend = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(consolehend, m); }
5.需要注意的一點(diǎn)是,由此結(jié)束后,一定要手動(dòng)釋放雙向鏈表占用的堆空間:
//退出游戲前,手動(dòng)銷毀鏈表中各個(gè)節(jié)點(diǎn) void ExitGame(pNode *pHead) { pNode p_delete = NULL, p_head = NULL; while (*pHead != NULL) { p_head = (*pHead)->next; if (p_head != NULL) p_head->pre = NULL; p_delete = *pHead; free(p_delete); p_delete = NULL; *pHead = p_head; } }
無(wú)論是靜態(tài)鏈表還是動(dòng)態(tài)鏈表,有時(shí)在解決具體問(wèn)題時(shí),需要我們對(duì)其結(jié)構(gòu)進(jìn)行稍微地調(diào)整。比如,可以把鏈表的兩頭連接,使其成為了一個(gè)環(huán)狀鏈表,通常稱為循環(huán)鏈表。
只需要將表中最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn),鏈表就能成環(huán)兒
需要注意的是,雖然循環(huán)鏈表成環(huán)狀,但本質(zhì)上還是鏈表,因此在循環(huán)鏈表中,依然能夠找到頭指針和首元節(jié)點(diǎn)等。循環(huán)鏈表和普通鏈表相比,唯一的不同就是循環(huán)鏈表首尾相連,其他都完全一樣。
約瑟夫環(huán)問(wèn)題,是一個(gè)經(jīng)典的循環(huán)鏈表問(wèn)題,題意是:已知 n 個(gè)人(分別用編號(hào) 1,2,3,…,n 表示)圍坐在一張圓桌周?chē)?,從編?hào)為 k 的人開(kāi)始順時(shí)針報(bào)數(shù),數(shù)到 m 的那個(gè)人出列;他的下一個(gè)人又從 1 開(kāi)始,還是順時(shí)針開(kāi)始報(bào)數(shù),數(shù)到 m 的那個(gè)人又出列;依次重復(fù)下去,直到圓桌上剩余一個(gè)人。
如圖 2 所示,假設(shè)此時(shí)圓周周?chē)?5 個(gè)人,要求從編號(hào)為 3 的人開(kāi)始順時(shí)針數(shù)數(shù),數(shù)到 2 的那個(gè)人出列:
俄羅斯輪盤(pán)是一個(gè)殘忍的游戲,具體規(guī)則為:游戲的道具是一把左輪手槍,其規(guī)則也很簡(jiǎn)單:在左輪手槍中的 6 個(gè)彈槽中隨意放入一顆或者多顆子彈,在任意旋轉(zhuǎn)轉(zhuǎn)輪之后,關(guān)上轉(zhuǎn)輪。游戲的參加者輪流把手槍對(duì)著自己,扣動(dòng)扳機(jī):中槍或是怯場(chǎng),即為輸?shù)囊环?;?jiān)持到最后的即為勝者。
本節(jié)實(shí)踐項(xiàng)目同輪盤(pán)賭類似,游戲規(guī)則:n 個(gè)參加者排成一個(gè)環(huán),每次由主持向左輪手槍中裝一顆子彈,并隨機(jī)轉(zhuǎn)動(dòng)關(guān)上轉(zhuǎn)輪,游戲從第一個(gè)人開(kāi)始,輪流拿槍;中槍者退出賭桌,退出者的下一個(gè)人作為第一人開(kāi)始下一輪游戲。直至最后剩余一個(gè)人,即為勝者。要求:模擬輪盤(pán)賭的游戲規(guī)則,找到游戲的最終勝者。
決類似的問(wèn)題,使用線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能實(shí)現(xiàn),根據(jù)游戲規(guī)則,在使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)只需使用循環(huán)鏈表即可輕松解決問(wèn)題。
#include <stdio.h> #include <stdlib.h> #include <time.h> //鏈表節(jié)點(diǎn)單元 typedef struct GameMan{ int Man; struct GameMan * next; }GameMan; //建立游戲人員循環(huán)鏈表 void InitGameManLine(GameMan **GameMans,int PersonNum){ *GameMans=(GameMan *)malloc(sizeof(GameMan));//頭指針指向首元節(jié)點(diǎn) //節(jié)點(diǎn)初始化 (*GameMans)->next=NULL; (*GameMans)->Man=1; GameMan *tail=*GameMans;//指向鏈表尾 for (int i=2;i<=PersonNum;i++){ GameMan *newnode=(GameMan *)malloc(sizeof(GameMan));//申請(qǐng)新節(jié)點(diǎn) //節(jié)點(diǎn)初始化 newnode->next=NULL; newnode->Man=i; tail->next=newnode;//將新節(jié)點(diǎn)鏈接到鏈表尾 tail=tail->next;//移動(dòng)tail到尾指針 } tail->next=*GameMans;//將鏈表成環(huán) } //輸出鏈表中所有游戲成員 void display(GameMan *GameMans){ GameMan *temp=GameMans; while (temp->next!=GameMans){ printf("%d ",temp->Man); temp=temp->next; } printf("%d\n\n",temp->Man); } int main() { GameMan *GameMans=NULL;//游戲成員鏈表頭指針 int round=1; int PersonNum; int BulletPos; // srand((int)time(0));//使用當(dāng)前時(shí)間作為rand()函數(shù)的隨機(jī)數(shù)的種子 srand((unsigned) time(NULL)); printf("請(qǐng)輸入本次游戲人數(shù)(<100): "); scanf("%d",&PersonNum); printf("\n為編號(hào)為 1-%d 的游戲人員分配位置!\n\n",PersonNum); InitGameManLine(&GameMans,PersonNum); GameMan* lineNext=GameMans;//用于記錄每輪開(kāi)始的位置 //僅當(dāng)鏈表中只含有一個(gè)結(jié)點(diǎn)時(shí),即頭結(jié)點(diǎn)時(shí),退出循環(huán) while(GameMans->next!=GameMans){ BulletPos=rand()%6+1; printf("第 %d 輪游戲,從編號(hào)為 %d 的人開(kāi)始,槍在第 %d 次扣動(dòng)扳機(jī)時(shí)會(huì)響!\n\n",round,lineNext->Man,BulletPos); GameMan *temp=lineNext; //遍歷循環(huán)鏈表,找到將要?jiǎng)h除結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn) for (int i=1;i<BulletPos-1;i++){ temp=temp->next; } //如果子彈位置BulletPos==1,則要找到當(dāng)前節(jié)點(diǎn)的上一節(jié)點(diǎn) if(BulletPos==1){ while(temp->next!=lineNext){ temp=temp->next; } } printf("編號(hào)為 %d 的賭徒退出賭博,剩余賭徒編號(hào)依次為:",temp->next->Man); //將要?jiǎng)h除結(jié)點(diǎn)從鏈表中刪除,并釋放其占用空間 GameMan * del=temp->next;//記錄刪除節(jié)點(diǎn) temp->next=temp->next->next;//從鏈表中移除該節(jié)點(diǎn) if(del==GameMans)GameMans=GameMans->next;//如果刪除的是頭節(jié)點(diǎn),將頭節(jié)點(diǎn)的下一節(jié)點(diǎn)作為頭節(jié)點(diǎn) free(del);//釋放del節(jié)點(diǎn) display(GameMans); //下一輪開(kāi)始的位置 lineNext=temp->next; round++;//回合次數(shù)加一 } printf("最終勝利的游戲人員編號(hào)是:%d \n\n",GameMans->Man); return 0; }
運(yùn)行結(jié)果示例:
#include <stdio.h> #include <stdlib.h> #include <time.h> //鏈表節(jié)點(diǎn)單元 typedef struct GameMan{ int Man; struct GameMan * next; }GameMan; //建立游戲人員循環(huán)鏈表 void InitGameManLine(GameMan **GameMans,int PersonNum){ *GameMans=(GameMan *)malloc(sizeof(GameMan));//頭指針指向首元節(jié)點(diǎn) //節(jié)點(diǎn)初始化 (*GameMans)->next=NULL; (*GameMans)->Man=1; GameMan *tail=*GameMans;//指向鏈表尾 for (int i=2;i<=PersonNum;i++){ GameMan *newnode=(GameMan *)malloc(sizeof(GameMan));//申請(qǐng)新節(jié)點(diǎn) //節(jié)點(diǎn)初始化 newnode->next=NULL; newnode->Man=i; tail->next=newnode;//將新節(jié)點(diǎn)鏈接到鏈表尾 tail=tail->next;//移動(dòng)tail到尾指針 } tail->next=*GameMans;//將鏈表成環(huán) } //輸出鏈表中所有游戲成員 void display(GameMan *GameMans){ GameMan *temp=GameMans; while (temp->next!=GameMans){ printf("%d ",temp->Man); temp=temp->next; } printf("%d\n\n",temp->Man); } int main() { GameMan *GameMans=NULL;//游戲成員鏈表頭指針 int round=1; int PersonNum; int BulletPos; // srand((int)time(0));//使用當(dāng)前時(shí)間作為rand()函數(shù)的隨機(jī)數(shù)的種子 srand((unsigned) time(NULL)); printf("請(qǐng)輸入本次游戲人數(shù)(<100): "); scanf("%d",&PersonNum); printf("\n為編號(hào)為 1-%d 的游戲人員分配位置!\n\n",PersonNum); InitGameManLine(&GameMans,PersonNum); GameMan* lineNext=GameMans;//用于記錄每輪開(kāi)始的位置 //僅當(dāng)鏈表中只含有一個(gè)結(jié)點(diǎn)時(shí),即頭結(jié)點(diǎn)時(shí),退出循環(huán) while(GameMans->next!=GameMans){ BulletPos=rand()%6+1; printf("第 %d 輪游戲,從編號(hào)為 %d 的人開(kāi)始,槍在第 %d 次扣動(dòng)扳機(jī)時(shí)會(huì)響!\n\n",round,lineNext->Man,BulletPos); GameMan *temp=lineNext; //遍歷循環(huán)鏈表,找到將要?jiǎng)h除結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn) for (int i=1;i<BulletPos-1;i++){ temp=temp->next; } //如果子彈位置BulletPos==1,則要找到當(dāng)前節(jié)點(diǎn)的上一節(jié)點(diǎn) if(BulletPos==1){ while(temp->next!=lineNext){ temp=temp->next; } } printf("編號(hào)為 %d 的賭徒退出賭博,剩余賭徒編號(hào)依次為:",temp->next->Man); //將要?jiǎng)h除結(jié)點(diǎn)從鏈表中刪除,并釋放其占用空間 GameMan * del=temp->next;//記錄刪除節(jié)點(diǎn) temp->next=temp->next->next;//從鏈表中移除該節(jié)點(diǎn) if(del==GameMans)GameMans=GameMans->next;//如果刪除的是頭節(jié)點(diǎn),將頭節(jié)點(diǎn)的下一節(jié)點(diǎn)作為頭節(jié)點(diǎn) free(del);//釋放del節(jié)點(diǎn) display(GameMans); //下一輪開(kāi)始的位置 lineNext=temp->next; round++;//回合次數(shù)加一 } printf("最終勝利的游戲人員編號(hào)是:%d \n\n",GameMans->Man); return 0; }
以上就是“C語(yǔ)言單雙線性及循環(huán)鏈表怎么實(shí)現(xiàn)”這篇文章的所有內(nèi)容,感謝各位的閱讀!相信大家閱讀完這篇文章都有很大的收獲,小編每天都會(huì)為大家更新不同的知識(shí),如果還想學(xué)習(xí)更多的知識(shí),請(qǐng)關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。