? 線性表可以說是最常見的一種數(shù)據(jù)結(jié)構(gòu)了，在日常學習中使用也很多，今天用C語言實現(xiàn)以下簡單的線性表及基本操作。對于線性表來說可以分為順序存儲和鏈式存儲。順序存儲是提前分配一個連續(xù)的空間，可以實現(xiàn)隨機存取，一般采用數(shù)組實現(xiàn)；鏈式存儲的存儲空間不必是連續(xù)的，使用比較靈活，不會占用多余空間，一般采用指針實現(xiàn)現(xiàn)在我們要實現(xiàn)的是鏈式存儲。直接上代碼：

目錄

一、頭文件等準備部分：

二、定義以及初始化

三、判斷線性表是否為空

四、將線性表置空?

五、返回線性表元素個數(shù)

?六、返回第i個元素的值

七、找到第一個與給定元素相等的節(jié)點的位置?

八、在第i個元素之后加入新元素并將L長度加1?

九、刪除第i個元素之后將該元素的值返回并令表長度減一

十、輸出每個元素的值?

十一、頭插法?

十二、尾插法?

十三、主函數(shù)定義?

---

一、頭文件等準備部分：

//線性表的鏈式存儲 #include <stdio.h> #include <string.h> #include <ctype.h> #include <stdlib.h> #include <io.h> #include <math.h> #include <time.h>//定義狀態(tài)常量 #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0#define MAXSIZE 20 /* 存儲空間初始分配量 */ typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */ typedef int ElemType; /* ElemType類型根據(jù)實際情況而定，這里假設(shè)為int */

二、定義以及初始化

鏈式存儲結(jié)構(gòu)的每個節(jié)點分為數(shù)據(jù)域data以及指針域，數(shù)據(jù)域存儲數(shù)據(jù)，指針域存儲結(jié)構(gòu)體指針，指向的是下一個節(jié)點。具體如圖所示：?

//定義結(jié)構(gòu)體 typedef struct Node{ElemType data;struct Node* next; }Node;

//定義線性表 typedef struct Node* LinkList;//初始化線性表 Status InitList(LinkList *L){*L=(LinkList)malloc(sizeof(Node)); /* 產(chǎn)生頭結(jié)點,并使L指向此頭結(jié)點 */if(!(*L)) /* 存儲分配失敗 */return ERROR;(*L)->next=NULL; /* 指針域為空 */return OK; }

?這里需要解釋幾點：

typedef （struct Node*） LinkList 這句可以加上括號理解，意思就是將指向Node類型的指針重新命名為Linklist，這樣做的目的主要是方便表示指向指針的指針（禁止套娃）

?*L=(LinkList)malloc(sizeof(Node))：*是取內(nèi)容運算符，則*L表示的指向節(jié)點的指針，malloc函數(shù)是動態(tài)申請一個節(jié)點

??????????????

這個線性表的頭節(jié)點生成了，并且next暫時為NULL之后的節(jié)點只需要接上就好，這里說一下頭節(jié)點：頭節(jié)點是沒有實際內(nèi)容的節(jié)點，僅僅是為了將插入、刪除等操作統(tǒng)一起來

三、判斷線性表是否為空

/* 初始條件：順序線性表L已存在。操作結(jié)果：若L為空表，則返回TRUE，否則返回FALSE */ Status ListEmpty(LinkList L) { if(L->next)return FALSE;elsereturn TRUE; }

四、將線性表置空?

/* 初始條件：順序線性表L已存在。操作結(jié)果：將L重置為空表 */ Status ClearList(LinkList *L) { LinkList p,q;p=(*L)->next; /* p指向第一個結(jié)點 */while(p) /* 沒到表尾 */{q=p->next;free(p);p=q;}(*L)->next=NULL; /* 頭結(jié)點指針域為空 */return OK; }

?有的同學可能發(fā)現(xiàn)了，在這個函數(shù)的形式參數(shù)定義為（Linlist *L）即指向指針的指針,而上一個函數(shù)定義為（Linklist L）即指向結(jié)構(gòu)體的指針，只是為啥呢？因為C語言的值傳遞機制，如果大家有興趣可以看看我的這篇文章。第三個函數(shù)僅僅是遍歷操作，并未涉及到傳參操作，不需要再多定義一個指針；第四個參數(shù)涉及到參數(shù)值的改變，如果單純在函數(shù)中進行值的傳遞，對主函數(shù)中原有參數(shù)的值是沒有任何影響的。大約就是下圖的意思哈哈哈哈

五、返回線性表元素個數(shù)

/* 初始條件：順序線性表L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個數(shù) */ int ListLength(LinkList L) {int i=0;LinkList p=L->next; /* p指向第一個結(jié)點 */while(p) {i++;p=p->next;}return i; }

同樣沒有參數(shù)值的改變，不需要指向指針的指針。

?六、返回第i個元素的值

/* 初始條件：順序線性表L已存在，1≤i≤ListLength(L) */ /* 操作結(jié)果：用e返回L中第i個數(shù)據(jù)元素的值 */ Status GetElem(LinkList L,int i,ElemType *e) {int j;LinkList p; /* 聲明一結(jié)點p */p = L->next; /* 讓p指向鏈表L的第一個結(jié)點 */j = 1; /* j為計數(shù)器 */while (p && j<i) /* p不為空或者計數(shù)器j還沒有等于i時，循環(huán)繼續(xù) */{ p = p->next; /* 讓p指向下一個結(jié)點 */++j;}if ( !p || j>i ) return ERROR; /* 第i個元素不存在 */*e = p->data; /* 取第i個元素的數(shù)據(jù) */return OK; }

七、找到第一個與給定元素相等的節(jié)點的位置?

/* 初始條件：順序線性表L已存在 */ /* 操作結(jié)果：返回L中第1個與e滿足關(guān)系的數(shù)據(jù)元素的位序。*/ /* 若這樣的數(shù)據(jù)元素不存在，則返回值為0 */ int LocateElem(LinkList L,ElemType e) {int i=0;LinkList p=L->next;while(p){i++;if(p->data==e) /* 找到這樣的數(shù)據(jù)元素 */return i;p=p->next;}return 0; }

八、在第i個元素之后加入新元素并將L長度加1?

/* 初始條件：順序線性表L已存在,1≤i≤ListLength(L)， */ /* 操作結(jié)果：在L中第i個位置之后插入新的數(shù)據(jù)元素e，L的長度加1 */ Status ListInsert(LinkList *L,int i,ElemType e) { int j;LinkList p,s;p = *L; j = 1;while (p && j<i) /* 尋找第i個結(jié)點 */{p = p->next;++j;} if (!p || j > i) return ERROR; /* 第i個元素不存在 */s = (LinkList)malloc(sizeof(Node)); /* 生成新結(jié)點(C語言標準函數(shù)) */s->data = e; s->next = p->next; /* 將p的后繼結(jié)點賦值給s的后繼 */p->next = s; /* 將s賦值給p的后繼 */return OK; }

九、刪除第i個元素之后將該元素的值返回并令表長度減一

/* 初始條件：順序線性表L已存在，1≤i≤ListLength(L) */ /* 操作結(jié)果：刪除L的第i個數(shù)據(jù)元素，并用e返回其值，L的長度減1 */ Status ListDelete(LinkList *L,int i,ElemType *e) { int j;LinkList p,q;p = *L;j = 1;while (p->next && j < i) /* 遍歷尋找第i個元素 */{p = p->next;++j;}if (!(p->next) || j > i) return ERROR; /* 第i個元素不存在 */q = p->next;p->next = q->next; /* 將q的后繼賦值給p的后繼 */*e = q->data; /* 將q結(jié)點中的數(shù)據(jù)給e */free(q); /* 讓系統(tǒng)回收此結(jié)點，釋放內(nèi)存 */return OK; }

十、輸出每個元素的值?

/* 初始條件：順序線性表L已存在 */ /* 操作結(jié)果：依次對L的每個數(shù)據(jù)元素輸出 */ Status ListTraverse(LinkList L) {LinkList p=L->next; /* p指向第一個結(jié)點 */while(p){visit(p->data);p=p->next;}printf("\t");return OK; }

十一、頭插法?

/* 隨機產(chǎn)生n個元素的值，建立帶表頭結(jié)點的單鏈線性表L（頭插法） */ void CreateListHead(LinkList *L, int n) {LinkList p;int i;srand(time(0)); /* 初始化隨機數(shù)種子 */*L = (LinkList)malloc(sizeof(Node));(*L)->next = NULL; /* 先建立一個帶頭結(jié)點的單鏈表 */for (i=0; i<n; i++) {p = (LinkList)malloc(sizeof(Node)); /* 生成新結(jié)點 */p->data = rand()%100+1; /* 隨機生成100以內(nèi)的數(shù)字 */p->next = (*L)->next; (*L)->next = p; /* 插入到表頭 */} }

說一下頭插法是從頭創(chuàng)建一個鏈表與在鏈表中插入一個元素不是一個意思，頭插法即每次新元素都是在表頭插入

十二、尾插法?

/* 隨機產(chǎn)生n個元素的值，建立帶表頭結(jié)點的單鏈線性表L（尾插法） */ void CreateListTail(LinkList *L, int n) {LinkList p,r;int i;srand(time(0)); /* 初始化隨機數(shù)種子 */*L = (LinkList)malloc(sizeof(Node)); /* L為整個線性表 */r=*L; /* r為指向尾部的結(jié)點 */for (i=0; i<n; i++) {p = (Node *)malloc(sizeof(Node)); /* 生成新結(jié)點 */p->data = rand()%100+1; /* 隨機生成100以內(nèi)的數(shù)字 */r->next=p; /* 將表尾終端結(jié)點的指針指向新結(jié)點 */r = p; /* 將當前的新結(jié)點定義為表尾終端結(jié)點 */}r->next = NULL; /* 表示當前鏈表結(jié)束 */ }

在尾插法中添加了一個尾指針。方便進行尾部的插入。?

十三、主函數(shù)定義?

int main() { LinkList L;ElemType e;Status i;int j,k;i=InitList(&L);printf("初始化L后：ListLength(L)=%d\n",ListLength(L));for(j=1;j<=5;j++)i=ListInsert(&L,1,j);printf("在L的表頭依次插入1～5后：L.data=");ListTraverse(L); printf("ListLength(L)=%d \n",ListLength(L));i=ListEmpty(L);printf("L是否空：i=%d(1:是 0:否)\n",i);i=ClearList(&L);printf("清空L后：ListLength(L)=%d\n",ListLength(L));i=ListEmpty(L);printf("L是否空：i=%d(1:是 0:否)\n",i);for(j=1;j<=10;j++)ListInsert(&L,j,j);printf("在L的表尾依次插入1～10后：L.data=");ListTraverse(L); printf("ListLength(L)=%d \n",ListLength(L));ListInsert(&L,1,0);printf("在L的表頭插入0后：L.data=");ListTraverse(L); printf("ListLength(L)=%d \n",ListLength(L));GetElem(L,5,&e);printf("第5個元素的值為：%d\n",e);for(j=3;j<=4;j++){k=LocateElem(L,j);if(k)printf("第%d個元素的值為：%d\n",k,j);elseprintf("沒有值為%d的元素\n",j);}k=ListLength(L); /* k為表長 */for(j=k+1;j>=k;j--){i=ListDelete(&L,j,&e); /* 刪除第j個數(shù)據(jù) */if(i==ERROR)printf("刪除第%d個數(shù)據(jù)失敗\n",j);elseprintf("刪除第%d個的元素值為：%d\n",j,e);}printf("依次輸出L的元素：");ListTraverse(L); j=5;ListDelete(&L,j,&e); /* 刪除第5個數(shù)據(jù) */printf("刪除第%d個的元素值為：%d\n",j,e);printf("依次輸出L的元素：");ListTraverse(L); i=ClearList(&L);printf("\n清空L后：ListLength(L)=%d\n",ListLength(L));CreateListHead(&L,20);printf("整體創(chuàng)建L的元素(頭插法)：");ListTraverse(L); i=ClearList(&L);printf("\n刪除L后：ListLength(L)=%d\n",ListLength(L));CreateListTail(&L,20);printf("整體創(chuàng)建L的元素(尾插法)：");ListTraverse(L); return 0; }

運行結(jié)果：?

這樣一個線性表就寫好了，代碼基本上就是《大話數(shù)據(jù)結(jié)構(gòu)》這本書的代碼，這本書真的很棒，與興趣的同學可以看一看。?

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的用C语言撸线性表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。