???????C語(yǔ)言實(shí)現(xiàn)單鏈表基本操作方法
更新時(shí)間：2022年05月16日 09:43:58 作者：??蘇州程序大白????
這篇文章主要介紹了???????C語(yǔ)言實(shí)現(xiàn)單鏈表基本操作方法，文章圍繞主題展開(kāi)詳細(xì)介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下
存儲(chǔ)結(jié)構(gòu)
typedef int dataType；//愛(ài)護(hù)據(jù)類型
typedef struct Node {
DataType data; // 結(jié)點(diǎn)數(shù)據(jù)
struct Node *next; // 指向下一個(gè)結(jié)點(diǎn)的指針
} Node, *LinkList;基本功能
- 頭插法創(chuàng)建單鏈表void CreateListHead( LinkList &head)
- 尾插法創(chuàng)建單鏈表void CreateListTail( LinkList &head)
- 獲取指定位置的元素 int GetElement(LinkList head, int i, DataType &e)
- 獲取指定元素的位置 int LocateElement(LinkList head, int e)
- 在指定位置插入元素 int InsertList(LinkList head, int i, DataType e)
- 刪除指定位置的元素 int DeleteList(LinkList head, int i, DataType &e)
- 獲取單鏈表的長(zhǎng)度 int LengthLinkList(LinkList head)
- 合并兩個(gè)非遞減的單鏈表 void MergeList(LinkList La, LinkList Lb, LinkList &Lc)
- 寂鏈表void Destroy( LinkList &L)
- 遍歷打印單鏈表中的所有元素 void PrintList(LinkList head)
頭插法創(chuàng)建單鏈表
每次添加鏈的結(jié)點(diǎn)都能找到頭結(jié)點(diǎn)的第1號(hào)位置，所以創(chuàng)建單表中的元素的順序是輸入元素的逆序。 ?
/**
* 頭插法創(chuàng)建單鏈表，輸入以-1結(jié)束
*/
void CreateListHead(LinkList &head) {
DataType x;
LinkList p;
head = (LinkList)malloc(LEN);
head->next = NULL;
scanf("%d", &x);
while (x != -1) {
p = (LinkList)malloc(LEN);
p->data = x;
p->next = head->next; // 新增的結(jié)點(diǎn)指向頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
head->next = p; // 頭結(jié)點(diǎn)指向新增的結(jié)點(diǎn)
scanf("%d", &x);
}
}尾插法創(chuàng)建單鏈表
每次新增的結(jié)點(diǎn)都放在單鏈表的后面，接下來(lái)和接下來(lái)的順序保持一致。 ?
/**
* 尾插法創(chuàng)建單鏈表，輸入以-1結(jié)束
*/
void CreateListTail(LinkList &head) {
LinkList p, q;
DataType x;
head = (LinkList)malloc(LEN);
q = head;
scanf("%d", &x);
while (x != -1) {
p = (LinkList)malloc(LEN);
p->data = x;
q->next = p;
q = p;
scanf("%d", &x);
}
q->next = NULL;
}獲取指定位置的元素
/**
* 獲取指定位置的元素
* @param head 指向單鏈表頭結(jié)點(diǎn)的指針（頭指針）
* @param i 位置
* @param e 用來(lái)存放對(duì)應(yīng)位置的元素值
* @return 0：獲取失??；1：獲取成功
*/
int GetElement(LinkList head, int i, DataType &e) {
LinkList p = head->next;
int j = 1;
while (p && j < i) { // 依次后移，直至為空或到達(dá)位置
p = p->next;
j++;
}
if (!p || j > i) { // p為空表示位置超過(guò)最大位置，j > i表示位置不合法(i < 1)
return 0;
}
e = p->data;
return 1;
}在指定位置插入元素
/**
* 在單鏈表插入元素到位置i
* @param head 單鏈表的頭指針
* @param i 插入位置
* @param e 插入元素
* @return 1：插入成功，0：插入失敗
*/
int InsertList(LinkList head, int i, DataType e) {
LinkList p = head; // 從頭結(jié)點(diǎn)開(kāi)始
int j = 1;
while (p && j < i) { // 找到插入位置的前一個(gè)結(jié)點(diǎn)
p = p->next;
j++;
}
if (!p || j > i) { // p為空或i < 1，插入位置不合法
return 0;
}
LinkList q = (LinkList)malloc(LEN); // 創(chuàng)建新結(jié)點(diǎn)
q->data = e;
q->next = p->next; // 將新結(jié)點(diǎn)指向前一個(gè)結(jié)點(diǎn)的后一個(gè)結(jié)點(diǎn)
p->next = q; // 前一個(gè)結(jié)點(diǎn)指向新結(jié)點(diǎn)
// 執(zhí)行上述兩個(gè)操作后，達(dá)到的效果是新結(jié)點(diǎn)插入到了前一個(gè)結(jié)點(diǎn)的后面
}刪除指定位置的元素
/**
* 刪除指定位置的元素
* @param head
* @param i 位置
* @param e 被刪除的元素的值存放在e中
* @return 1：刪除成功，0：刪除失敗
*/
int DeleteList(LinkList head, int i, DataType &e) {
LinkList p = head;
int j = 1;
while (p && j < i) { // 找到位置的前一個(gè)結(jié)點(diǎn)
p = p->next;
j++;
}
if (!p || j > i) {
return 0;
}
LinkList s = p->next;
e = s->data;
p->next = s->next; // 改變前一個(gè)結(jié)點(diǎn)的指向，使其指向刪除結(jié)點(diǎn)的后一個(gè)結(jié)點(diǎn)
free(s);
return 1;
}獲取單鏈表的長(zhǎng)度
/**
* 獲取單鏈表的長(zhǎng)度
* @param head
* @return 單鏈表的長(zhǎng)度
*/
int LengthLinkList(LinkList head) {
LinkList p = head->next;
int count = 0;
while (p) {
count++;
p = p->next;
}
return count;
}合并兩個(gè)非遞減的單鏈表
合并兩個(gè)非遞減的單鏈，新鏈表仍然保持非遞減。 ?
/**
* 合并兩個(gè)非遞減的單鏈表，新的鏈表仍然非遞減
* @param La
* @param Lb
* @param Lc
*/
void MergeList(LinkList La, LinkList Lb, LinkList &Lc) {
LinkList pa, pb, pc;
pa = La->next;
pb = Lb->next;
pc = Lc = (LinkList)malloc(LEN);
while (pa && pb) {
if (pa->data <= pb->data) {
pc->next = pa;
pc = pa;
pa = pa->next;
} else {
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
pc->next = pa ? pa : pb;
free(Lb);
}晴鏈表
/**
* 銷(xiāo)毀鏈表
*/
void Destroy(LinkList &L) {
LinkList p, q;
p = L;
while (p) { // 遍歷所有結(jié)點(diǎn)，釋放內(nèi)存
q = p;
p = p->next;
free(q);
}
L = NULL; // L置為NULL
}
遍歷打印單鏈表
/**
* 遍歷打印單鏈表的所有元素
*/
void PrintList(LinkList head) {
LinkList p = head->next;
if (p == NULL) {
cout << "List is NULL!" <<endl;
} else {
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
}
附上完整代碼
#include<cstdlib>
using namespace std;
#define LEN sizeof(Node)
typedef int DataType;
typedef struct Node {
DataType data;
struct Node *next;
} Node, *LinkList;
/**
* 頭插法創(chuàng)建單鏈表
* @param head
*/
void CreateListHead(LinkList &head) {
DataType x;
LinkList p;
head = (LinkList)malloc(LEN);
head->next = NULL;
scanf("%d", &x);
while (x != -1) {
p = (LinkList)malloc(LEN);
p->data = x;
p->next = head->next;
head->next = p;
scanf("%d", &x);
}
}
/**
* 尾插法創(chuàng)建單鏈表
* @param head
*/
void CreateListTail(LinkList &head) {
LinkList p, q;
DataType x;
head = (LinkList)malloc(LEN);
q = head;
scanf("%d", &x);
while (x != -1) {
p = (LinkList)malloc(LEN);
p->data = x;
q->next = p;
q = p;
scanf("%d", &x);
}
q->next = NULL;
}
/**
* 獲取指定位置的元素
* @param head 單鏈表頭指針
* @param i 位置
* @param e 獲取的元素賦值該參數(shù)
* @return 0：獲取失??；1：獲取成功
*/
int GetElement(LinkList head, int i, DataType &e) {
LinkList p = head->next;
int j = 1;
while (p && j < i) {
p = p->next;
j++;
}
if (!p || j > i) {
return 0;
}
e = p->data;
return 1;
}
/**
* 獲取某個(gè)元素的位置
* @param head
* @param e
* @return 元素的位置
*/
int LocateElement(LinkList head, int e) {
LinkList p = head->next;
int j = 1;
while (p && p->data != e) {
p = p->next;
j++;
}
if (!p) {
return 0;
}
return j;
}
/**
* 在單鏈表插入元素到位置i
* @param head 單鏈表的頭指針
* @param i 插入位置
* @param e 插入元素
* @return 1：插入成功，0：插入失敗
*/
int InsertList(LinkList head, int i, DataType e) {
LinkList p = head;
int j = 1;
while (p && j < i) {
p = p->next;
j++;
}
if (!p || j > i) {
return 0;
}
LinkList q = (LinkList)malloc(LEN);
q->data = e;
q->next = p->next;
p->next = q;
}
/**
* 刪除指定位置的元素
* @param head
* @param i 位置
* @param e 被刪除的元素的值存放在e中
* @return 1：刪除成功，0：刪除失敗
*/
int DeleteList(LinkList head, int i, DataType &e) {
LinkList p = head;
int j = 1;
while (p && j < i) {
p = p->next;
j++;
}
if (!p || j > i) {
return 0;
}
LinkList s = p->next;
e = s->data;
p->next = s->next;
free(s);
return 1;
}
/**
* 獲取單鏈表的長(zhǎng)度
* @param head
* @return
*/
int LengthLinkList(LinkList head) {
LinkList p = head->next;
int count = 0;
while (p) {
count++;
p = p->next;
}
return count;
}
/**
* 合并兩個(gè)非遞減的單鏈表，新的鏈表仍然非遞減
* @param La
* @param Lb
* @param Lc
*/
void MergeList(LinkList La, LinkList Lb, LinkList &Lc) {
LinkList pa, pb, pc;
pa = La->next;
pb = Lb->next;
pc = Lc = (LinkList)malloc(LEN);
while (pa && pb) {
if (pa->data <= pb->data) {
pc->next = pa;
pc = pa;
pa = pa->next;
} else {
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
pc->next = pa ? pa : pb;
free(Lb);
}
/**
* 銷(xiāo)毀鏈表
* @param L
*/
void Destroy(LinkList &L) {
LinkList p, q;
p = L;
while (p) {
q = p;
p = p->next;
free(q);
}
L = NULL;
}
/**
* 遍歷打印單鏈表的所有元素
* @param head
*/
void PrintList(LinkList head) {
LinkList p = head->next;
if (p == NULL) {
cout << "List is NULL!" <<endl;
} else {
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
}
int main() {
LinkList L;
printf("頭插法創(chuàng)建單鏈表：（輸入以-1結(jié)束）\n");
CreateListHead(L);
PrintList(L);
printf("尾插法創(chuàng)建單鏈表：（輸入以-1結(jié)束）\n");
CreateListTail(L);
PrintList(L);
InsertList(L, 1, 100);
printf("在1號(hào)位置插入100后，單鏈表如下：\n");
PrintList(L);
DataType e;
DeleteList(L, 1, e);
printf("刪除1號(hào)位置的元素，被刪除的元素為：\n");
printf("刪除后的單鏈表為：\n");
PrintList(L);
printf("單鏈表的長(zhǎng)度為：%d\n", LengthLinkList(L));
GetElement(L, 1, e);
printf("1號(hào)位置的元素為：%d\n");
printf("元素4在單鏈表中的位置為：%d\n", LocateElement(L, 4));
cout << endl;
LinkList La, Lb, Lc;
printf("尾插法創(chuàng)建單鏈表La：\n");
CreateListTail(La);
PrintList(La);
printf("尾插法創(chuàng)建單鏈表Lb：\n");
CreateListTail(Lb);
PrintList(Lb);
MergeList(La, Lb, Lc);
printf("合并單鏈表La和Lb后的新單鏈表Lc如下：\n");
PrintList(Lc);
return 0;
}運(yùn)行結(jié)果：
注意：
寫(xiě)法采用了C++引用參數(shù)的寫(xiě)法，LinkList &head，C語(yǔ)言下不支持這種寫(xiě)法，需要在C++環(huán)境下使用，即.cpp文件。
下面附上C語(yǔ)言的：
/**
* LinkList 本身已經(jīng)是結(jié)構(gòu)體指針，參數(shù)再使用LinkList *的形式
* 可以理解為要想改變一個(gè)結(jié)構(gòu)體指針，則需要取指針的指針。
* 類似于改變int a，則需要使用 int *a，這里要改變LinkList head，則需要使用LinkList *head
*/
void CreatListTail(LinkList *head) {
int x;
LinkList *p, *q;
*head = (LinkList *) malloc(LEN);
q = *head;
scanf("%d", &x);
while (x != -1) {
p = (LinkList *) malloc(LEN);
p->data = x;
q->next = p;
q = p;
scanf("%d", &x);
}
q->next = NULL;
}
// 可以不傳參，函數(shù)里面定義頭指針，創(chuàng)建鏈表，然后把頭指針?lè)祷?，主函?shù)用結(jié)構(gòu)體指針接收即可
LinkList CreateListhead() {
int x;
LinkList *head, *p;
head = (LinkList *) malloc(LEN);
head->next = NULL;
scanf("%d", &x);
while (x != -1) {
p = (LinkList *) malloc(LEN);
p->data = x;
p->next = head->next;
head->next = p;
}
return head;
}到此這篇關(guān)于C語(yǔ)言實(shí)現(xiàn)單鏈表基本操作方法的文章就介紹到這了,更多相關(guān)C語(yǔ)言單鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
在本篇文章當(dāng)中主要給大家介紹C語(yǔ)言當(dāng)中一些不常用的特性，比如在main函數(shù)之前和之后設(shè)置我們想要執(zhí)行的函數(shù)，以及各種花式退出程序的方式，需要的可以參考一下2022-10-10
求解微分方程的數(shù)值解一般使用MATLAB等數(shù)值計(jì)算軟件，其實(shí)C++也可以求解微分方程，需要用到odeint庫(kù)，它是boost庫(kù)的一部分。官方教程和示例比較晦澀，本文力求用較短的篇幅介紹它的基本用法,需要的朋友可以參考下面文章的具體內(nèi)容2021-09-09
C++中利用cout和fstream采用非科學(xué)計(jì)數(shù)法輸出
這篇文章主要介紹了C++中利用cout和fstream采用非科學(xué)計(jì)數(shù)法輸出方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-11-11
C語(yǔ)言實(shí)現(xiàn)計(jì)算器的兩種方法
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)計(jì)算器的兩種方法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-01-01
c++11?實(shí)現(xiàn)枚舉值到枚舉名的轉(zhuǎn)換問(wèn)題
這篇文章主要介紹了c++11?實(shí)現(xiàn)枚舉值到枚舉名的轉(zhuǎn)換,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-03-03
這篇文章主要介紹了距離詳解Linux下的UDP方式通訊,是深入Linux系統(tǒng)編程中的基礎(chǔ),需要的朋友可以參考下2015-10-10
這篇文章主要介紹了c語(yǔ)言讀取csv文件和c++讀取csv文件示例,需要的朋友可以參考下2014-03-03
這篇文章主要介紹了C++選擇排序算法實(shí)例,本文先是介紹了什么是選擇排序,然后給出了實(shí)現(xiàn)代碼,需要的朋友可以參考下2014-10-10
這篇文章主要介紹了C++模板template原理，函數(shù)模板代表了一個(gè)函數(shù)家族，該函數(shù)模板與類型無(wú)關(guān)，在使用時(shí)被參數(shù)化，根據(jù)實(shí)參類型產(chǎn)生函數(shù)的特定類型版本2022-07-07
關(guān)于C++虛函數(shù)與靜態(tài)、動(dòng)態(tài)綁定的問(wèn)題
這篇文章主要介紹了C++虛函數(shù)與靜態(tài)、動(dòng)態(tài)綁定,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-10-10