目錄

每日文案

一、線性表的定義

二、線性表的操作

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

順序表的初始化操作?

判斷順序表是否為空表

將順序表置為空表

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

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

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

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

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

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

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

總結(jié)

---

每日文案

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

---

一、線性表的定義

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

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

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

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

二、線性表的操作

• 順序表的存儲結(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          /* 存儲空間初始分配量 */
typedef int ElemType;       /* ElemType類型根據(jù)實際情況而定，這里假設(shè)為int */
typedef struct
{ElemType data[MAXSIZE]; /* 數(shù)組，存儲數(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;
}

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

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

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

/* 初始條件：順序線性表L已存在，1≤i≤ListLength(L) */
/* 操作結(jié)果：用e返回L中第i個數(shù)據(jù)元素的值,注意i是指位置，第1個位置的數(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個與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ù)向后移動一位然后再把數(shù)據(jù)插入

/* 初始條件：順序線性表L已存在,1≤i≤ListLength(L)， */
/* 操作結(jié)果：在L中第i個位置之前插入新的數(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比第一位置小或者比最后一位置后一位置還要大時 */return ERROR;if (i<=L->length)        /* 若插入數(shù)據(jù)位置不在表尾 */{for(k=L->length-1;k>=i-1;k--)  /* 將要插入位置之后的數(shù)據(jù)元素向后移動一位 */L->data[k+1]=L->data[k];}L->data[i-1]=e;          /* 將新元素插入 */L->length++;return OK;
}

?

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

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

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

/* 初始條件：順序線性表L已存在，1≤i≤ListLength(L) */
/* 操作結(jié)果：刪除L的第i個數(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的每個數(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個數(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)，給我堅持住了