目錄
鏈式存儲結構
代碼實現(xiàn)
鏈表初始化
頭插法(前插法)創(chuàng)建含k個結點的單鏈表
尾插法(后插法)創(chuàng)建含k個結點的單鏈表
取第i個節(jié)點的數(shù)據(jù)域
尋找數(shù)據(jù)域等于e的結點返回該結點序號
在第i個結點插入數(shù)據(jù)域為e的結點
刪除第i個結點
遍歷鏈表
求鏈表結點個數(shù)(鏈表長度）
銷毀鏈表
合并兩個鏈表
鏈式存儲結構
用一組物理位置任意的存儲單元來存放線性表的數(shù)據(jù)元素
這組存儲單元既可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內存中的任一位置上的
鏈表中元素的邏輯次序和物理次序不一定相同
結點：數(shù)據(jù)元素的存儲映像，由數(shù)據(jù)域和指針域兩部分組成
鏈表：n個結點由指針鏈組成一個鏈表
結點只有一個指針域的鏈表稱為單鏈表或者線性鏈表
結點有兩個指針域的鏈表，稱為雙鏈表
首尾相接的鏈表稱為循環(huán)鏈表
什么時候是空表
無頭結點時，頭指針為空時表示空表
有頭結點時，當頭結點的指針域為空時表示空表
在鏈表中設置頭結點的好處
1.便于首元結點的處理：首元結點的地址保存在頭結點的指針域中，所以在鏈表的第一個位置上的操作和其他位置一致，無需進行特殊處理
2.便于空表和非空表的統(tǒng)一處理：無論鏈表是否為空，頭指針都是指向頭結點的非空指針，因此空表和非空表的處理也就統(tǒng)一了
頭結點的數(shù)據(jù)域
頭結點的數(shù)據(jù)域可以為空，也可存放線性表長度等附加信息，頭結點不能計入鏈表長度值
鏈式存儲結構的特點
1.在存儲器中的位置是任意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰
2.訪問時只能通過頭指針進入鏈表，并通過每個結點的指針域依次向后順序掃描其余結點，所以尋找第一個結最后一結點所花的時間不等
這存取元素的方法被稱為順序存取法
優(yōu)點：結點空間可以動態(tài)申請和釋放
數(shù)據(jù)元素的邏輯次序靠結點的指針來指示，插入和刪除時不需要移動數(shù)據(jù)元素。
缺點：存儲密度小，每個結點的指針域需要額外占用存儲空間，當每個節(jié)點的數(shù)據(jù)與所占字節(jié)不多時，指針域所占存儲空間的比重顯得很大
存儲密度：
存儲密度是指結點數(shù)據(jù)本身所占的存儲量和整個結點結構中所占的存儲量之比，即：
存儲密度=結點數(shù)據(jù)本身占用的空間/節(jié)點占用的空間總量
一般地，存儲密度越大，存儲空間的利用率就越高，顯然，順序表的存儲密度為1（100%），而鏈表的存儲密度小于一。
鏈式存儲結構是非隨機存取的結構，對任一節(jié)點的操作都要從頭指針依指針鏈查找到該結點，這增加了算法的復雜度
代碼實現(xiàn)
注：許多課程里調用函數(shù)時函數(shù)的形參用&S，但這個&S好像在c語言編譯器會報錯，應該是c++可以實現(xiàn)，所以c語言在函數(shù)調用時還是定義一個指針變量以實現(xiàn)各種操作。文章來源：http://www.zghlxwxcb.cn/news/detail-720411.html
鏈表初始化
int Initlist(linklist* S) //鏈表初始化
{
(*S) = (linklist)malloc(sizeof(Lnode));
if (!(*S)) {
printf("鏈表初始化失敗！\n");
return error;
}
(*S)->next = NULL;
printf("鏈表初始化完畢！\n");
return ok;
}頭插法(前插法)創(chuàng)建含k個結點的單鏈表
int headlist(linklist* S, int k) //頭插法(前插法)創(chuàng)建含n個結點的單鏈表
{
int i;
linklist p;
for (i = k; i>0; i--) {
p = (linklist)malloc(sizeof(Lnode));
printf("請輸入第%d個結點的數(shù)據(jù)：\n",i);
scanf_s("%d", &(p->data));
p->next = (*S)->next;
(*S)->next = p;
}
printf("頭插法創(chuàng)建單鏈表成功！\n");
return ok;
}尾插法(后插法)創(chuàng)建含k個結點的單鏈表
int endlist(linklist* S, int k) ? ?//尾插法(后插法)創(chuàng)建含k個結點的單鏈
{
?? ?int i;
?? ?linklist p,q=(*S);
?? ?for (i = 0; i < k; i++) {
?? ??? ?p = (linklist)malloc(sizeof(Lnode));
?? ??? ?printf("請輸入第%d個結點的數(shù)據(jù)：\n", i + 1);
?? ??? ?scanf_s("%d", &(p->data));
?? ??? ?p->next = NULL;
?? ??? ?q->next = p;
?? ??? ?q = p;
?? ?}
?? ?printf("尾插法創(chuàng)建單鏈表成功！\n");
?? ?return ok;
}取第i個節(jié)點的數(shù)據(jù)域
int getlist(linklist S, int i) ? ?取第i個節(jié)點的數(shù)據(jù)域
{
?? ?int j=0;
?? ?linklist p;
?? ?p = S;
?? ?while (p && j < i) {
?? ??? ?p = p->next;
?? ??? ?j++;
?? ?}
?? ?if (!p || j > i) {
?? ??? ?printf("該節(jié)點不存在！\n");
?? ??? ?return error;
?? ?}
?? ?printf("該結點數(shù)據(jù)為%d \n", p->data);
?? ?return ok;
}尋找數(shù)據(jù)域等于e的結點返回該結點序號
int locatelist(linklist S, int e) //尋找數(shù)據(jù)域等于e的結點返回該結點序號
{
int j = 1;
linklist p=S->next;
while (p && p->data != e) {
p = p->next;
j++;
}
if (!p) {
printf("未找到和該數(shù)據(jù)相等結點！\n");
return error;
}
printf("該結點序號為%d \n",j);
return ok;
}在第i個結點插入數(shù)據(jù)域為e的結點
int insertlist(linklist* S, int i, int e) //在第i個結點插入數(shù)據(jù)域為e的結點
{
int j=0;
linklist p = (*S),q;
q = (linklist)malloc(sizeof(Lnode));
while (p && j < i - 1) {
p = p->next;
j++;
}
if (i <= 0 || !p) {
printf("結點溢出,插入失敗！\n");
return error;
}
q->data = e;
q->next = p->next;
p->next = q;
printf("數(shù)據(jù)插入完畢！\n");
return ok;
}刪除第i個結點
int deletelist(linklist* S, int i) //刪除第i個結點
{
int j=0;
linklist p, q;
p = (*S);
if (i <= 0 && !(p->next)) {
printf("程序錯誤,刪除失敗!\n");
return error;
}
while (p->next && j < i - 1) {
p = p -> next;
j++;
}
q = p->next;
printf("被刪除的結點元素是%d \n", q->data);
p ->next = q->next;
free(q);
return ok;
}遍歷鏈表
int printlist(linklist S) //遍歷鏈表
{
int i=1;
linklist p;
p = S->next;
if (!p) {
printf("鏈表為空無法遍歷！\n");
return error;
}
while (p) {
printf("第%d個結點的數(shù)據(jù)域是:%d\n",i,p->data);
p = p->next;
i++;
}
return ok;
}求鏈表結點個數(shù)(鏈表長度）
int lengthlist(linklist S) //求鏈表結點個數(shù)(鏈表長度）
{
int j=1;
linklist p=S->next;
if (!p) {
printf("鏈表為空！\n");
}
while (p->next) {
p = p->next;
j++;
}
printf("該鏈表有%d個結點 \n",j);
return ok;
}銷毀鏈表
int destorylist(linklist* S) //銷毀鏈表
{
linklist p=(*S);
while (!p) {
p = p->next;
free(*S);
}
printf("該鏈表已銷毀！\n");
return ok;
}合并兩個鏈表
int merge(linklist* S1, linklist* S2,linklist *S3) //合并兩個鏈表
{
linklist pa, pb, pc;
pa = (*S1)->next;
pb = (*S2)->next;
pc=(*S3) = (*S1);
while (pa && pb) {
if (pa->data <= pb->data) {
pc->next = pa;
pa = pa->next;
pc = pc->next;
}
else {
pc->next = pb;
pb = pb->next;
pc = pc->next;
}
}
if (!pa) {
pc->next = pb;
}
else {
pc -> next = pa;
}
return ok;
}總代碼實現(xiàn)文章來源地址http://www.zghlxwxcb.cn/news/detail-720411.html
#include<stdio.h>
#include<stdlib.h>
#define ok 1
#define error 0
typedef struct {
int data;
struct Lnode* next;
}Lnode,*linklist;
int Initlist(linklist* S); //鏈表初始化
int headlist(linklist* S,int k); //頭插法(前插法)創(chuàng)建含k個結點的單鏈表
int endlist(linklist* S, int k); //尾插法(后插法)創(chuàng)建含k個結點的單鏈表
int getlist(linklist S, int i); //取第i個節(jié)點的數(shù)據(jù)域保存在*e中
int locatelist(linklist S, int e); //尋找數(shù)據(jù)域等于e的結點返回該結點序號
int insertlist(linklist* S, int i, int e); //在第i個結點插入數(shù)據(jù)域為e的結點
int deletelist(linklist* S,int i); //刪除第i個結點
int printlist(linklist S); //遍歷鏈表
int lengthlist(linklist S); //求鏈表結點個數(shù)(鏈表長度）
int destorylist(linklist* S); //銷毀鏈表
int merge(linklist* S1, linklist* S2,linklist *S3); //合并兩個鏈表
int main()
{
linklist La, Lb,Lc;
int i,j,k, n,m;
j=Initlist(&La);
if (!j) {
return error;
}
j=Initlist(&Lb);
if (!j) {
return error;
}
printf("請輸入La的結點數(shù)：\n");
scanf_s("%d", &n);
headlist(&La, n);
printlist(La);
printf("請輸入Lb的結點數(shù)：\n");
scanf_s("%d", &n);
endlist(&Lb, n);
printlist(Lb);
printf("請輸入想獲取的La的結點數(shù)據(jù)的序號：\n");
scanf_s("%d", &k);
getlist(La, k);
printf("請輸入La中想要尋找的數(shù)據(jù)：\n");
scanf_s("%d", &m);
locatelist(La,m);
printf("請輸入想要插入La的結點序號以及數(shù)據(jù)：\n");
scanf_s("%d %d", &n, &m);
insertlist(&La, n, m);
lengthlist(La);
printlist(La);
printf("請輸入想要刪除La中的結點序號：\n");
scanf_s("%d", &n);
deletelist(&La, n);
printlist(La);
lengthlist(La);
merge(&La, &Lb,&Lc);
printlist(Lc);
destorylist(&La);
destorylist(&Lb);
return 0;
}
int Initlist(linklist* S) //鏈表初始化
{
(*S) = (linklist)malloc(sizeof(Lnode));
if (!(*S)) {
printf("鏈表初始化失??！\n");
return error;
}
(*S)->next = NULL;
printf("鏈表初始化完畢！\n");
return ok;
}
int headlist(linklist* S, int k) //頭插法(前插法)創(chuàng)建含n個結點的單鏈表
{
int i;
linklist p;
for (i = k; i>0; i--) {
p = (linklist)malloc(sizeof(Lnode));
printf("請輸入第%d個結點的數(shù)據(jù)：\n",i);
scanf_s("%d", &(p->data));
p->next = (*S)->next;
(*S)->next = p;
}
printf("頭插法創(chuàng)建單鏈表成功！\n");
return ok;
}
int endlist(linklist* S, int k) //尾插法(后插法)創(chuàng)建含k個結點的單鏈
{
int i;
linklist p,q=(*S);
for (i = 0; i < k; i++) {
p = (linklist)malloc(sizeof(Lnode));
printf("請輸入第%d個結點的數(shù)據(jù)：\n", i + 1);
scanf_s("%d", &(p->data));
p->next = NULL;
q->next = p;
q = p;
}
printf("尾插法創(chuàng)建單鏈表成功！\n");
return ok;
}
int getlist(linklist S, int i) //取第i個節(jié)點的數(shù)據(jù)域保存在*e中
{
int j=0;
linklist p;
p = S;
while (p && j < i) {
p = p->next;
j++;
}
if (!p || j > i) {
printf("該節(jié)點不存在！\n");
return error;
}
printf("該結點數(shù)據(jù)為%d \n", p->data);
return ok;
}
int locatelist(linklist S, int e) //尋找數(shù)據(jù)域等于e的結點返回該結點序號
{
int j = 1;
linklist p=S->next;
while (p && p->data != e) {
p = p->next;
j++;
}
if (!p) {
printf("未找到和該數(shù)據(jù)相等結點！\n");
return error;
}
printf("該結點序號為%d \n",j);
return ok;
}
int insertlist(linklist* S, int i, int e) //在第i個結點插入數(shù)據(jù)域為e的結點
{
int j=0;
linklist p = (*S),q;
q = (linklist)malloc(sizeof(Lnode));
while (p && j < i - 1) {
p = p->next;
j++;
}
if (i <= 0 || !p) {
printf("結點溢出,插入失??！\n");
return error;
}
q->data = e;
q->next = p->next;
p->next = q;
printf("數(shù)據(jù)插入完畢！\n");
return ok;
}
int deletelist(linklist* S, int i) //刪除第i個結點
{
int j=0;
linklist p, q;
p = (*S);
if (i <= 0 && !(p->next)) {
printf("程序錯誤,刪除失敗!\n");
return error;
}
while (p->next && j < i - 1) {
p = p -> next;
j++;
}
q = p->next;
printf("被刪除的結點元素是%d \n", q->data);
p ->next = q->next;
free(q);
return ok;
}
int printlist(linklist S) //遍歷鏈表
{
int i=1;
linklist p;
p = S->next;
if (!p) {
printf("鏈表為空無法遍歷！\n");
return error;
}
while (p) {
printf("第%d個結點的數(shù)據(jù)域是:%d\n",i,p->data);
p = p->next;
i++;
}
return ok;
}
int lengthlist(linklist S) //求鏈表結點個數(shù)(鏈表長度）
{
int j=1;
linklist p=S->next;
if (!p) {
printf("鏈表為空！\n");
}
while (p->next) {
p = p->next;
j++;
}
printf("該鏈表有%d個結點 \n",j);
return ok;
}
int destorylist(linklist* S) //銷毀鏈表
{
linklist p=(*S);
while (!p) {
p = p->next;
free(*S);
}
printf("該鏈表已銷毀！\n");
return ok;
}
int merge(linklist* S1, linklist* S2,linklist *S3) //合并兩個鏈表
{
linklist pa, pb, pc;
pa = (*S1)->next;
pb = (*S2)->next;
pc=(*S3) = (*S1);
while (pa && pb) {
if (pa->data <= pb->data) {
pc->next = pa;
pa = pa->next;
pc = pc->next;
}
else {
pc->next = pb;
pb = pb->next;
pc = pc->next;
}
}
if (!pa) {
pc->next = pb;
}
else {
pc -> next = pa;
}
return ok;
}到了這里，關于鏈表的基本操作（c語言）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
