線性表

定義

線性表是具有相同特性數據類型的n個數據元素的有限序列。其中n為表長，n=0為空表。

結構

開始結點 -a1- 前驅結點 - a2-后繼結點 - an-終端結點

特點

• 表中元素的個數有限

• 表中元素具有邏輯上的順序性，表中元素有其先后次序
• 表中元素都是數據元素，每個元素都是單個元素
• 每個元素占有相同大小的存儲空間?

注意

線性表是一種邏輯結構，表示元素之間的一對一關系?

總結

?

• 線性表中地元素的類型可以為簡單類型（int char float...），也可以是復雜類型(例如：姓名、班級、電話號碼)?
• 許多實際應用問題所設計的基本操作有很大相似性，不應該為每個具體應用單獨編寫一個程序。
• 從具體應用中抽象出共性的邏輯結構和基本操作（抽象數據類型），然后實現其存儲結構和基本操作。

????????例如：存放學生的學號，姓名，成績

typedef struct {char num[8]; //數據域char name[8]; //數據域int score; //數據域}ElemType;typedef struct {ElemType data;int length }List;

順序表

定義

線性表的順序存儲又稱順序表

用一組地址連續的存儲單元依次存儲線性表的數據元素

特點

利用數據元素的存儲位置表示線性表中相鄰數據元素之間的前后關系，即線性表的邏輯結構與存儲結構一致（在順序表中，邏輯相鄰的兩個元素存儲位置上也相鄰）

在訪問線性表時，可以快速地計算出任何一個數據元素地存儲地址，因此可以粗略地認為，訪問每個元素所花地時間相等。（這種存取元素地方法被稱為隨機存取法）

順序表的順序存儲表示

由于順序表（元素）地址連續，依次存取，隨機存取，類型相同，與數組概念一樣，我們用一維數組表示順序表

注意：數組長度不可動態定義，但線性長度不可動態定義。解決方法，定義一個表長的變量。

?一維數組空間分配

靜態分配：數組大小和空間已經固定，一旦空間占滿，在加入新的數據會產生溢出，程序會崩潰

動態分配：一旦數據空間占滿，就另外開辟一塊空間更大的存儲空間，用以替換原來的空間?

動態分配概念如下：

?

?int *q;

q=(int *)malloc(sizeof(int)*MAXSIZE)

定義了一個地址，將改地址附上空間，便可以存儲內容

?

?順序表優缺點

優點

• 存儲密度大（結點本身所占存儲量/結點結構所占存儲量、與鏈表對比）
• 可隨機存取表中任一元素

缺點

• 在插入、刪除某一元素時，需要移動大量元素
• 浪費存儲空間
• 屬于靜態存儲形式，數據元素的個數不能自由擴充

順序表重要的操作

?ListInsert（）//在線性表中第i個位置插入新元素? **********重點操作

void ListInsert(List *L){int i;ElemType x;printf_s("請輸入插入的位置\n");scanf_s("%d", &i);printf_s("請輸入插入的值\n");scanf_s("%d", &x);//判斷表是否滿了if (L->length == MAXSIZE) {printf_s("表滿");exit(1);}//判斷插入的位置是否合法if (i<1 || i>L->length+1) {printf_s("該表不存在");exit(1);}//將插入位置的值及后面的值全部往后移動一位for (int j = L->length; j >= i; j--) {L->a[j] = L->a[j - 1];}L->length++;L->a[i - 1] = x; }

思路：

判斷表是否滿了（無法插入）

判斷插入位置，是否合法（注意：插入的位置，可以是最前面，也可以值最后面，故可插入的位置應該 ‘length+1’）

全部符合條件，將插入的位置的值及后面的值全部往后移動一位，從尾部執行判斷

缺點：需要移動大量元素

ListDelete() //刪除線性表L中第i個元素? ? ******重點操作

void ListDelete(List *L){int i;printf_s("請輸入要刪除的位置\n");scanf_s("%d", &i);//判斷位置是否合法if (i<1 || i>L->length) {printf_s("該位置不合法\n");exit(1);}//符合條件，將插入位置后面的元素全部往前移動一個位置，從表尾開始判斷for (int j = L->length; j > i; j--) {L->a[j - 2] = L->a[j - 1];}//表長減1L->length--; }

第二步可以或

for (int j = i; j < L->length; j++) {L->a[j - 1] = L->a[j];}

思路

• 判斷插入位置是否合法
• 全部符合條件，將刪除的元素位置后的元素全部往前移動一個位置，length-1；

缺點：需要移動大量元素

LocateElem（）//查找第一個相同元素的位置

void LocateElem(List L) {ElemType x;int i=1;printf_s("請輸入你要查找位置的值\n");scanf_s("%d", &x);for (i ; L.length >= i; i++) {if(L.a[i-1] == x)printf_s("該位置是%d", i);}}

?或判斷為：

while (L.length >= i && L.a[i - 1] != x)i++;printf_s("該位置是%d", i);

思路：

• 需要一個一個比較值是否相等，從鏈表頭開始
• 如果值相當跳出循序

?void InitLIsit()//初始化表

void InitList(List *L) {L->length = 0; }

?思路：

將表長置于0，即置空表

?

void IsEmpty //判斷線性表是否為空

void IsEmpty(List L) {if (L.length == 0)printf_s("該表為空");elseprintf_s("該表非空"); }

void DestroyList（）與void ClearList()

//刪除線性表，刪地址 void DestroyList(List *L) {if (L->length)free(L); } //清空線線性表，留地址 void ClearList(List *L) {L->length == 0; }

思路：

銷毀線性表：銷毀改該線性表的地址，不能在存放任何東西

清空線性表：將表長清零，即內容清零，地址留下

類似一個把杯子摔壞，一個倒掉里面的水

void ListLength()//求該表的表長

void ListLength(List L) {int x;x = L.length;printf_s("該表長為%d"); }

void GetElem() //獲取第i個元素的值

void GetElem(List L) {int i;ElemType x;printf_s("請輸入要查找的位置");scanf_s("%d", &i);if (i<1 && i>L.length) {printf_s("該值不合法");exit(1);}elsex = L.a[i - 1];printf_s("該位置上的值是%d", x);}

思路：

判斷查找的值是否合法

優點：

隨時存取

輸入輸出void printList?() 和 void CreateList()//方便代碼測試

//輸出表 void printList(List L) {int i;for (i = 0; i < L.length; i++) {printf_s("%5d", L.a[i]);}printf_s("\n"); }//創建表 void CreateList(List *L) {ElemType x;printf_s("請輸入一組數據以'0'為結束符\n");scanf_s("%d", &x);while(x){L->a[L->length++] = x;scanf_s("%d", &x);}}

以下是全部代碼：

#include<stdio.h> #include<stdlib.h> #define MAXSIZE 5 typedef int ElemType;typedef struct {ElemType a[MAXSIZE];int length; }List; //插入元素 void ListInsert(List *L){int i;ElemType x;printf_s("請輸入插入的位置\n");scanf_s("%d", &i);printf_s("請輸入插入的值\n");scanf_s("%d", &x);//判斷表是否滿了if (L->length == MAXSIZE) {printf_s("表滿");exit(1);}//判斷插入的位置是否合法if (i<1 || i>L->length+1) {printf_s("該表不存在");exit(1);}//將插入位置的值及后面的值全部往后移動一位for (int j = L->length; j >= i; j--) {L->a[j] = L->a[j - 1];}L->length++;L->a[i - 1] = x; } //刪除位置的元素 void ListDelete(List *L){int i;printf_s("請輸入要刪除的位置\n");scanf_s("%d", &i);if (i<1 || i>L->length) {printf_s("該位置不合法\n");exit(1);}for (int j = L->length; j > i; j--) {L->a[j - 2] = L->a[j - 1];}L->length--;} //輸出 void printList(List L) {int i;for (i = 0; i < L.length; i++) {printf_s("%5d", L.a[i]);}printf_s("\n"); } //初始化 void InitList(List *L) {L->length = 0; } //創建表 void CreateList(List *L) {ElemType x;printf_s("請輸入一組數據以'0'為結束符\n");scanf_s("%d", &x);while(x){L->a[L->length++] = x;scanf_s("%d", &x);}} //判斷表是否為空 void IsEmpty(List L) {if (L.length == 0)printf_s("該表為空");elseprintf_s("該表非空"); } //按值查找位置 void LocateElem(List L) {ElemType x;int i=1;printf_s("請輸入你要查找位置的值\n");scanf_s("%d", &x);while (L.length >= i && L.a[i - 1] != x)i++;printf_s("該位置是%d", i);} //刪除線性表，刪地址 void DestroyList(List *L) {if (L->length)free(L); } //清空線線性表，留地址 void ClearList(List *L) {L->length == 0; } //獲取表長 void ListLength(List L) {int x;x = L.length;printf_s("該表長為%d"); } //獲取第i個元素位置上的值 void GetElem(List L) {int i;ElemType x;printf_s("請輸入要查找的位置");scanf_s("%d", &i);if (i<1 && i>L.length) {printf_s("該值不合法");exit(1);}elsex = L.a[i - 1];printf_s("該位置上的值是%d", x);}main() {List L;InitList(&L);CreateList(&L);printList(L);}

總結

以上是生活随笔為你收集整理的数据结构之线性表及C语言实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。