目錄

每日文案

一、線性表的定義

二、線性表的操作

順序表的存儲(chǔ)結(jié)構(gòu)

順序表的初始化操作?

判斷順序表是否為空表

將順序表置為空表

?計(jì)算順序表中的元素個(gè)數(shù)

取出順序表中的對應(yīng)位置元素

?取出對應(yīng)數(shù)值的位序

?在對應(yīng)位置插入元素

將對應(yīng)位置的元素刪除

?將順序表中的數(shù)據(jù)打印出來

?將順序表A和B進(jìn)行合并

總結(jié)

---

每日文案

失去的東西,其實(shí)從來未曾真正屬于的屬于你,也不必惋惜

---

一、線性表的定義

????????線性表是:零個(gè)或者多個(gè)數(shù)據(jù)元素的有限序列

????????這里我強(qiáng)調(diào)幾個(gè)地方,首先是序列，那么就是有序的，如果說有多個(gè)元素，那么第一個(gè)元素就沒有前驅(qū)的,最后一個(gè)元素是沒有后繼的，其他的元素有且僅有一個(gè)前驅(qū)和后繼。就像是幼兒園開小火車，如果一個(gè)小朋友去拉后面兩個(gè)小朋友的衣服那么就不可以排成一隊(duì)了，如果多個(gè)小朋友拉扯那就是在打架了.

? ? ? ? 然后線性表強(qiáng)調(diào)的是有限性,線性元素的個(gè)數(shù)n定義為線性表的長度,如果n=0那么線性表就是一個(gè)空表,并且每個(gè)數(shù)據(jù)元素都有確定的位置,比如說a1是第一個(gè)元素，那么他的位序就是1 同理Ai 就是在線性表的位序就是i?

? ? ? ? 這里舉個(gè)例子,班級同學(xué)的花名冊,其中包含著同學(xué)的學(xué)號(hào)，姓名，性別等等信息構(gòu)成一個(gè)表這個(gè)也是一個(gè)線性表，這里需要強(qiáng)調(diào)一個(gè)概念，在復(fù)雜的線性表中，一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成,這里我們表格里面的姓名學(xué)號(hào)這些都是數(shù)據(jù)項(xiàng)，他們連起來構(gòu)成了數(shù)據(jù)元素，最后串起來構(gòu)成了數(shù)據(jù)項(xiàng)

二、線性表的操作

• 順序表的存儲(chǔ)結(jié)構(gòu)

#include "stdio.h"    #include "stdlib.h"  
#include "math.h"  
#include "time.h"#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0#define MAXSIZE 20          /* 存儲(chǔ)空間初始分配量 */
typedef int ElemType;       /* ElemType類型根據(jù)實(shí)際情況而定，這里假設(shè)為int */
typedef struct
{ElemType data[MAXSIZE]; /* 數(shù)組，存儲(chǔ)數(shù)據(jù)元素 */int length;             /* 線性表當(dāng)前長度 */
}SqList;typedef int Status;         /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */

• 順序表的初始化操作?

/* 初始化順序線性表 */
Status InitList(SqList *L) 
{ L->length=0;return OK;
}

• 判斷順序表是否為空表

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

• 將順序表置為空表

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

• ?計(jì)算順序表中的元素個(gè)數(shù)

/* 初始條件：順序線性表L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個(gè)數(shù) */
int ListLength(SqList L)
{return L.length;
}

• 取出順序表中的對應(yīng)位置元素

/* 初始條件：順序線性表L已存在，1≤i≤ListLength(L) */
/* 操作結(jié)果：用e返回L中第i個(gè)數(shù)據(jù)元素的值,注意i是指位置，第1個(gè)位置的數(shù)組是從0開始 */
Status GetElem(SqList L,int i,ElemType *e)
{if(L.length==0 || i<1 || i>L.length)return ERROR;*e=L.data[i-1];return OK;
}

• ?取出對應(yīng)數(shù)值的位序

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

• ?在對應(yīng)位置插入元素

????????第一步先是判斷完順序表的狀態(tài)是否是滿的,插入位置是否合法

????????第二步判斷是否在表尾,在表尾就直接插入,不在表尾需要將原來位置的數(shù)據(jù)向后移動(dòng)一位然后再把數(shù)據(jù)插入

/* 初始條件：順序線性表L已存在,1≤i≤ListLength(L)， */
/* 操作結(jié)果：在L中第i個(gè)位置之前插入新的數(shù)據(jù)元素e，L的長度加1 */
Status ListInsert(SqList *L,int i,ElemType e)
{ int k;if (L->length==MAXSIZE)  /* 順序線性表已經(jīng)滿 */return ERROR;if (i<1 || i>L->length+1)/* 當(dāng)i比第一位置小或者比最后一位置后一位置還要大時(shí) */return ERROR;if (i<=L->length)        /* 若插入數(shù)據(jù)位置不在表尾 */{for(k=L->length-1;k>=i-1;k--)  /* 將要插入位置之后的數(shù)據(jù)元素向后移動(dòng)一位 */L->data[k+1]=L->data[k];}L->data[i-1]=e;          /* 將新元素插入 */L->length++;return OK;
}

?

• 將對應(yīng)位置的元素刪除

? ? ? ? 第一步也是先判斷順序表狀態(tài)

? ? ? ? 第二步把后面的數(shù)據(jù)往前移動(dòng)進(jìn)行數(shù)據(jù)覆蓋,我們不能直接對內(nèi)存中的數(shù)據(jù)進(jìn)行操作,只能將后面的數(shù)據(jù)進(jìn)行覆蓋

/* 初始條件：順序線性表L已存在，1≤i≤ListLength(L) */
/* 操作結(jié)果：刪除L的第i個(gè)數(shù)據(jù)元素，并用e返回其值，L的長度減1 */
Status ListDelete(SqList *L,int i,ElemType *e) 
{ int k;if (L->length==0)               /* 線性表為空 */return ERROR;if (i<1 || i>L->length)         /* 刪除位置不正確 */return ERROR;*e=L->data[i-1];if (i<L->length)                /* 如果刪除不是最后位置 */{for(k=i;k<L->length;k++)/* 將刪除位置后繼元素前移 */L->data[k-1]=L->data[k];}L->length--;return OK;
}

• ?將順序表中的數(shù)據(jù)打印出來

/* 初始條件：順序線性表L已存在 */
/* 操作結(jié)果：依次對L的每個(gè)數(shù)據(jù)元素輸出 */
Status ListTraverse(SqList L)
{int i;for(i=0;i<L.length;i++)visit(L.data[i]);printf("\n");return OK;
}

• ?將順序表A和B進(jìn)行合并

/*將所有的在線性表Lb中但不在La中的數(shù)據(jù)元素插入到La中*/
void unionL(SqList *La,SqList Lb)
{int La_len,Lb_len,i;ElemType e;                        /*聲明與La和Lb相同的數(shù)據(jù)元素e*/La_len=ListLength(*La);            /*求線性表的長度 */Lb_len=ListLength(Lb);for (i=1;i<=Lb_len;i++){GetElem(Lb,i,&e);              /*取Lb中第i個(gè)數(shù)據(jù)元素賦給e*/if (!LocateElem(*La,e))        /*La中不存在和e相同數(shù)據(jù)元素*/ListInsert(La,++La_len,e); /*插入*/}
}

---

總結(jié)

本次對數(shù)據(jù)結(jié)構(gòu)中的順序表進(jìn)行講解，前路還有很遠(yuǎn)，給我堅(jiān)持住了