C語(yǔ)言單雙線性及循環(huán)鏈表與實(shí)例
鏈表思維
順序存儲(chǔ)結(jié)構(gòu)
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è)指針域,所以叫做單鏈表。
單鏈表存儲(chǔ)結(jié)構(gòu)
獲得鏈表第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ò)指向后面。我們要做的就是上一步
可以寫成 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)建
創(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)直接寫自由(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).
單鏈表實(shí)例
#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)門創(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;
}
單鏈表學(xué)生系統(tǒng)簡(jiǎn)單實(shí)例
此處使用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)門創(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.先寫鏈表，先寫數(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í)現(xiàn)貪吃蛇
貪吃蛇實(shí)例展示：
思想結(jié)構(gòu)分析：
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è)二維畫面中，定義一個(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;
}
}
循環(huán)鏈表
無(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)鏈表實(shí)現(xiàn)約瑟夫環(huán)
約瑟夫環(huán)問(wèn)題，是一個(gè)經(jīng)典的循環(huán)鏈表問(wèn)題，題意是：已知 n 個(gè)人（分別用編號(hào) 1，2，3，…，n 表示）圍坐在一張圓桌周圍，從編號(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í)圓周周圍有 5 個(gè)人，要求從編號(hào)為 3 的人開(kāi)始順時(shí)針數(shù)數(shù)，數(shù)到 2 的那個(gè)人出列：
實(shí)踐項(xiàng)目之俄羅斯輪盤賭小游戲
俄羅斯輪盤是一個(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)目同輪盤賭類似，游戲規(guī)則：n 個(gè)參加者排成一個(gè)環(huán)，每次由主持向左輪手槍中裝一顆子彈，并隨機(jī)轉(zhuǎn)動(dòng)關(guān)上轉(zhuǎn)輪，游戲從第一個(gè)人開(kāi)始，輪流拿槍；中槍者退出賭桌，退出者的下一個(gè)人作為第一人開(kāi)始下一輪游戲。直至最后剩余一個(gè)人，即為勝者。要求：模擬輪盤賭的游戲規(guī)則，找到游戲的最終勝者。
俄羅斯輪盤設(shè)計(jì)思路
決類似的問(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)題。
順序存儲(chǔ)結(jié)構(gòu)模擬輪盤
#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é)果示例：
鏈表實(shí)現(xià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;
}
到此這篇關(guān)于C語(yǔ)言單雙線性及循環(huán)鏈表與實(shí)例的文章就介紹到這了,更多相關(guān)C語(yǔ)言鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C++通過(guò)TerminateProess結(jié)束進(jìn)程實(shí)例
這篇文章主要介紹了C++通過(guò)TerminateProess結(jié)束進(jìn)程實(shí)例,是Windows應(yīng)用程序設(shè)計(jì)中非常實(shí)用的技巧,需要的朋友可以參考下2014-10-10
C語(yǔ)言實(shí)現(xiàn)銀行管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)銀行管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-01-01
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)發(fā)牌洗牌，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-05-05
C++中小數(shù)點(diǎn)輸出格式(實(shí)例代碼)
下面小編就為大家?guī)?lái)一篇C++中小數(shù)點(diǎn)輸出格式(實(shí)例代碼)。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-06-06
這篇文章主要給大家介紹了關(guān)于C語(yǔ)言之預(yù)處理命令的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-04-04
VSCode 搭建 Arm 遠(yuǎn)程調(diào)試環(huán)境的步驟詳解
這篇文章主要介紹了VSCode 搭建 Arm 遠(yuǎn)程調(diào)試環(huán)境的步驟詳解,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-04-04
這篇文章主要為大家詳細(xì)介紹了C++的程序流程結(jié)構(gòu)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2022-02-02
詳解C++的反調(diào)試技術(shù)與繞過(guò)手法
反調(diào)試技術(shù)，惡意代碼會(huì)用它識(shí)別自身是否被調(diào)試，或者讓調(diào)試器失效，給反病毒工程師們制造麻煩，拉長(zhǎng)提取特征碼的時(shí)間線，本章將具體總結(jié)常見(jiàn)的反調(diào)試基礎(chǔ)的實(shí)現(xiàn)原理以及如何過(guò)掉這些反調(diào)試手段，從而讓我們能夠繼續(xù)分析惡意代碼2021-06-06
C++ 標(biāo)準(zhǔn)模板庫(kù) STL 順序容器詳解
這篇文章主要介紹了C++ 標(biāo)準(zhǔn)模板庫(kù) STL 順序容器詳解,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-05-05
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)連連看游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-01-01