C語言線性表全面梳理操作方法
更新時間：2022年04月22日 14:49:49 作者：平凡的人1
線性表，數(shù)據(jù)結構中最簡單的一種存儲結構，專門用于存儲邏輯關系為"一對一"的數(shù)據(jù)。線性表是基于數(shù)據(jù)在實際物理空間中的存儲狀態(tài)，又可細分為順序表（順序存儲結構）和鏈表
線性表：零個或多個數(shù)據(jù)元素的有限序列
強調(diào)幾點：
- 首先它是一個序列。也就是說，元素之間是有順序的，若元素存在多個，則第一個元素無前驅，最后一個元素無后繼，其他都有一個前驅和后繼。
- 其次線性表強調(diào)是有限的。
線性表有兩種物理結構，第一種是順序存儲結構，另一種是鏈式存儲結構。
線性表的順序存儲結構，指的是用一段地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。用c語言的一維數(shù)組來實現(xiàn)順序存儲結構。
線性表順序存儲結構的優(yōu)缺點
優(yōu)點：
- 可以快速地讀取表中任一位置的元素
- 無需為表示表中元素之間的邏輯關系而增加額外的存儲空間
缺點：
- 插入和刪除操作需要移動大量元素
- 當線性表長度變化較大時，難以確定存儲空間的容量，造成存儲空間的“破碎”
實際上，順序存儲結構最大的缺點就是插入和刪除時需要移動大量元素，這顯然就需要耗費時間。于是我們迎來了線性表的第二種存儲結構：鏈式存儲結構
鏈式存儲結構的特點是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的。
在順序存儲結構中，每個數(shù)據(jù)元素之需要存儲數(shù)據(jù)元素信息就可以了?，F(xiàn)在鏈式結構中，除了要存儲數(shù)據(jù)元素信息外，還要存儲它的后繼元素的地址。
把存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，把存儲直接后繼位置的域稱為指針域
下面來說說鏈表的優(yōu)點在哪里
- 基于結構體指針
- 可動態(tài)地分配存儲
- 所有結點離散分布，僅由指針聯(lián)系起來
準備工作
頭文件
#include "stdio.h" #include "stdlib.h" #include "math.h" #include "time.h"
宏定義以及typedef的使用
#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 20 /* 存儲空間初始分配量 */ typedef int Status;/* Status是函數(shù)的類型,其值是函數(shù)結果狀態(tài)代碼，如OK等 */ typedef int ElemType;/* ElemType類型根據(jù)實際情況而定，這里假設為int */
結構體及其定義
typedef struct Node
{
ElemType data;
struct Node* next;
}Node;
typedef struct Node* LinkList; /* 定義LinkList */malloc函數(shù)
這里簡單說一下malloc函數(shù)的用法
指針自身=（指針類型*）malloc（sizeof（指針類型））
注：
- malloc返回的是無類型的指針，在使用時一定要強制轉換為所需類型
- 開辟空間后，一定要釋放空間，否則會造成內(nèi)存泄漏。
- free（p）函數(shù)，釋放p所指變量的存儲空間，徹底刪除一個變量
其他注意事項
- 當你傳遞一個參數(shù)給函數(shù)的時候，這個參數(shù)會不會在函數(shù)內(nèi)被改動決定了使用什么參數(shù)形式
- 如果需要被改動，則需要傳遞指向這個參數(shù)的指針
- 如果不需要被改動，可以直接傳遞這個參數(shù)。
請時刻注意這點，不要老是遇到函數(shù)一會要指針，一會不要指針的時候一頭霧水，搞不明白。
下面說一說單鏈表基本的操作
單鏈表的初始化（頭結點指針域置為空）
/* 初始化鏈式線性表 */
Status InitList(LinkList* L)
{
*L = (LinkList)malloc(sizeof(Node)); /* 產(chǎn)生頭結點,并使L指向此頭結點 */
if (!(*L)) /* 存儲分配失敗 */
return ERROR;
(*L)->next = NULL; /* 指針域為空 */
return OK;
}判斷鏈表是否為空（實際上就是根據(jù)頭結點是否為空?？辗祷?，非空返回0）
/* 初始條件：鏈式線性表L已存在。操作結果：若L為空表，則返回TRUE，否則返回FALSE */
Status ListEmpty(LinkList L)
{
if (L->next)
return FALSE;
else
return TRUE;清空鏈表
/* 初始條件：鏈式線性表L已存在。操作結果：將L重置為空表 */
Status ClearList(LinkList *L)
{
LinkList p,q;
p=(*L)->next; /* p指向第一個結點 */
while(p) /* 沒到表尾 */
{
q=p->next;
free(p);
p=q;
}
(*L)->next=NULL; /* 頭結點指針域為空 */
return OK;
}求鏈表的表長
/* 初始條件：鏈式線性表L已存在。操作結果：返回L中數(shù)據(jù)元素個數(shù) */
int ListLength(LinkList L)
{
int i = 0;
LinkList p = L->next; /* p指向第一個結點 */
while (p)
{
i++;
p = p->next;
}
return i;
}取值
/* 初始條件：鏈式線性表L已存在，1≤i≤ListLength(L) */
/* 操作結果：用e返回L中第i個數(shù)據(jù)元素的值 */
Status GetElem(LinkList L,int i,ElemType *e)
{
int j;
LinkList p; /* 聲明一結點p */
p = L->next; /* 讓p指向鏈表L的第一個結點 */
j = 1; /* j為計數(shù)器 */
while (p && j<i) /* p不為空或者計數(shù)器j還沒有等于i時，循環(huán)繼續(xù) */
{
p = p->next; /* 讓p指向下一個結點 */
++j;
}
if ( !p || j>i )
return ERROR; /* 第i個元素不存在 */
*e = p->data; /* 取第i個元素的數(shù)據(jù) */
return OK;
}按值查找
/* 初始條件：鏈式線性表L已存在 */
/* 操作結果：返回L中第1個與e滿足關系的數(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;
}插入
/* 初始條件：鏈式線性表L已存在,1≤i≤ListLength(L)， */
/* 操作結果：在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個結點 */
{
p = p->next;
++j;
}
if (!p || j > i)
return ERROR; /* 第i個元素不存在 */
s = (LinkList)malloc(sizeof(Node)); /* 生成新結點(C語言標準函數(shù)) */
s->data = e;
s->next = p->next; /* 將p的后繼結點賦值給s的后繼 */
p->next = s; /* 將s賦值給p的后繼 */
return OK;
}刪除
/* 初始條件：鏈式線性表L已存在，1≤i≤ListLength(L) */
/* 操作結果：刪除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結點中的數(shù)據(jù)給e */
free(q); /* 讓系統(tǒng)回收此結點，釋放內(nèi)存 */
return OK;
}單鏈表的建立——頭插法
/* 隨機產(chǎn)生n個元素的值，建立帶表頭結點的單鏈線性表L（頭插法） */
void CreateListHead(LinkList* L, int n)
{
LinkList p;
int i;
srand(time(0)); /* 初始化隨機數(shù)種子 */
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL; /* 先建立一個帶頭結點的單鏈表 */
for (i = 0; i < n; i++)
{
p = (LinkList)malloc(sizeof(Node)); /* 生成新結點 */
p->data = rand() % 100 + 1; /* 隨機生成100以內(nèi)的數(shù)字 */
p->next = (*L)->next;
(*L)->next = p; /* 插入到表頭 */
}
}單鏈表的建立——尾插法
/* 隨機產(chǎn)生n個元素的值，建立帶表頭結點的單鏈線性表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為指向尾部的結點 */
for (i = 0; i < n; i++)
{
p = (Node*)malloc(sizeof(Node)); /* 生成新結點 */
p->data = rand() % 100 + 1; /* 隨機生成100以內(nèi)的數(shù)字 */
r->next = p; /* 將表尾終端結點的指針指向新結點 */
r = p; /* 將當前的新結點定義為表尾終端結點 */
}
r->next = NULL; /* 表示當前鏈表結束 */
}注：關于p->data的數(shù)據(jù)你也可以改成手動輸入，不必讓它隨機產(chǎn)生
重要的是能理解頭插法或者尾插法的算法思想
輸出
/* 初始條件：鏈式線性表L已存在 */
/* 操作結果：依次對L的每個數(shù)據(jù)元素輸出 */
Status ListTraverse(LinkList L)
{
LinkList p = L->next;
while (p)
{
visit(p->data);
p = p->next;
}
printf("\n");
return OK;
}Status visit(ElemType c)
{
printf("%d ", c);
return OK;
}主函數(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);
else
printf("沒有值為%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);
else
printf("刪除第%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;
}到此這篇關于c語言線性表全面梳理操作方法的文章就介紹到這了,更多相關c語言線性表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要給大家介紹了關于C++輸入輸出重定向的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2018-09-09
這篇文章主要為大家詳細介紹了C語言基于EasyX繪制時鐘，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-06-06
基于OpenCV讀取攝像頭實現(xiàn)單個人臉驗證MFC程序
這篇文章主要為大家詳細介紹了基于OpenCV讀取攝像頭實現(xiàn)單個人臉驗證MFC程序，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-08-08
C++實現(xiàn)LeetCode(208.實現(xiàn)字典樹(前綴樹))
這篇文章主要介紹了C++實現(xiàn)LeetCode(208.實現(xiàn)字典樹(前綴樹)),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-08-08
C語言 TerminateProcess函數(shù)案例詳解
這篇文章主要介紹了C語言 TerminateProcess函數(shù)案例詳解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-08-08
這篇文章主要介紹了C++ 中將一維數(shù)組轉成多維的三種方式,每種方式結合實例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友參考下吧2023-12-12
這篇文章主要介紹了詳解C++中的數(shù)據(jù)抽象,數(shù)據(jù)抽象是指，只向外界提供關鍵信息，并隱藏其后臺的實現(xiàn)細節(jié)，即只表現(xiàn)必要的信息而不呈現(xiàn)細節(jié),需要的朋友可以參考下2023-05-05
滾動條(Trackbar)在OpenCV中是非常方便的交互工具,它依附于特定的窗口而存在,下面這篇文章主要給大家介紹了關于OpenCV?c++滑動條的創(chuàng)建和使用的相關資料,需要的朋友可以參考下2023-06-06
從下面表中的數(shù)據(jù)來看寫入用時vector和deque很快，因為他們內(nèi)存分配次數(shù)少，關聯(lián)容器和list都是一個一個分配的，一個一個分配也會造成內(nèi)存碎片，內(nèi)存利用率低2013-09-09
C++實現(xiàn)十進制數(shù)轉為其它進制數(shù)
這篇文章主要為大家詳細介紹了C++實現(xiàn)十進制數(shù)轉為其它進制數(shù)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-04-04