其他文章：
數(shù)據(jù)結(jié)構(gòu)之棧和隊(duì)列
文章目錄
1.1 概念
1.2 順序表
1.3 鏈表
1.4 兩種存儲(chǔ)方式的比較
1.5 兩種表的實(shí)現(xiàn)方式及其各種操作
1.5.1 順序表
1.5.2 單鏈表
1.6 應(yīng)用實(shí)例
1.1 概念
線性表是具有相同特性的數(shù)據(jù)元素的一個(gè)有限序列。
注：注意概念中的關(guān)鍵字政冻，線性表中的每一項(xiàng)叫數(shù)據(jù)元素，它是有限的。另外值得注意的是涯保，線性表是可以是空表仪召，即它的長(zhǎng)度是0時(shí)為空表印屁。
數(shù)據(jù)結(jié)構(gòu)中，線性表分為順序表和鏈表留量。
下面介紹兩種存儲(chǔ)形式的概念的特性以及兩者之間的比較。
1.2 順序表
順序表就是把線性表中的所有元素按照其邏輯順序哟冬，依次存儲(chǔ)到從指定的存
儲(chǔ)位置開始的一塊連續(xù)的存儲(chǔ)空間中楼熄。
注：說(shuō)白了，在C語(yǔ)言中浩峡，就是數(shù)組可岂，而數(shù)組的特點(diǎn)就是一塊連續(xù)的存儲(chǔ)空間。所謂的邏輯順序翰灾，按照我的理解缕粹，就是其排列的順序稚茅。或從小到大或者從大到小或者亂序致开，或者按照某個(gè)特定的規(guī)則排序峰锁。（不知道有沒有理解到位！Ｋ痢：缃！）
1.3 鏈表
在鏈表存儲(chǔ)中飒货，每個(gè)節(jié)點(diǎn)不僅包含所有元素本身的信息魄衅，還包含元素之間邏輯關(guān)系的信息，即前驅(qū)節(jié)點(diǎn)包含后繼節(jié)點(diǎn)的地址信息塘辅。
1.4 兩種存儲(chǔ)方式的比較：
1晃虫、順序表的特點(diǎn)：
1）隨機(jī)訪問特性。順序表在查找方面效率較高扣墩，只要知道下標(biāo)哲银，立馬就能獲取到該元素。
2）順序表要求占用連續(xù)的存儲(chǔ)空間呻惕。這是順序表的存儲(chǔ)結(jié)構(gòu)決定的荆责，它用數(shù)組表示，就必須是占用連續(xù)的存儲(chǔ)空間亚脆。
3）存儲(chǔ)分配只能預(yù)先進(jìn)行做院，即靜態(tài)分配。就像C語(yǔ)言中數(shù)組的聲明一樣濒持，需要在聲明的時(shí)候就需要確定其長(zhǎng)度键耕，例如int a[30];長(zhǎng)度為30的int型數(shù)組。
2柑营、鏈表的特點(diǎn)
1）不支持隨機(jī)訪問屈雄。因?yàn)殒湵碇忻總€(gè)元素的地址保存在其前驅(qū)節(jié)點(diǎn)中的指針域，所以要訪問該節(jié)點(diǎn)官套，必須知道其前驅(qū)節(jié)點(diǎn)棚亩，所以訪問節(jié)點(diǎn)每次都是從頭結(jié)點(diǎn)開始。
2）節(jié)點(diǎn)的存儲(chǔ)空間利用率較順序表稍低一些虏杰。
3）動(dòng)態(tài)分配存儲(chǔ)空間讥蟆。鏈表可以任意增加鏈表長(zhǎng)度和縮短鏈表長(zhǎng)度，這得益于它的結(jié)構(gòu)特點(diǎn)：鏈?zhǔn)健?/p>
注：順序表在做插入操作時(shí)需要移動(dòng)多個(gè)元素纺阔，而鏈表則不需要移動(dòng)任何元素瘸彤。
1.5 兩種表的實(shí)現(xiàn)方式及其各種操作
首先定義幾個(gè)常量，代碼如下（C/C++）：
#define MAXSIZE 100 //線性表的最大長(zhǎng)度
#define DataType int //數(shù)據(jù)的類型
1.5.1 順序表
線性表的定義只有兩個(gè)數(shù)據(jù)域笛钝，一個(gè)是存儲(chǔ)數(shù)據(jù)信息的數(shù)組质况，一個(gè)是保存線性表長(zhǎng)度的length變量愕宋。代碼如下：
typedef struct {
DataType data[MAXSIZE]; //數(shù)據(jù)域
int length; //順序表長(zhǎng)度
}SqList;
以下是順序表的各種操作
1.初始化操作
順序表的初始化操作只需要將length初始化為0即可.代碼如下:
void Init(SqList &L){
L.length = 0;
}
2、插入操作
插入操作可分為以下幾步(順序表的存儲(chǔ)開始位置為1):
(1) 判斷插入位置index的合法性以及l(fā)ength的合法性(也可以增加順序表的最大長(zhǎng)度).
(2)將第index個(gè)元素的后續(xù)元素后移一位.
(3)將e值插入index位置,并將length加1.
int Insert(SqList &L, int index, DataType e) {
//首先判斷index的合法性
//1 <= index <= length + 1, 元素開始下標(biāo)為1,可以插入順序表尾部
//L表的長(zhǎng)度也有限制结榄，必須小于定義的長(zhǎng)度 MAXSIZE - 1
if(index < 1 || index > L.length + 1 || L.length == MAXSIZE - 1) {
return 0; //插入失敗返回0
}
int i;
//參數(shù)合法中贝，開始插入操作
//1、先將需要移動(dòng)的元素移動(dòng)
for(i = L.length; i >= index; --i) {
L.data[i + 1] = L.data[i];
}
//2臼朗、最后index位置空著邻寿，將e插入
L.data[index] = e;
//3、長(zhǎng)度加1
L.length++;
return 1; //插入成功视哑，返回1
}
3.刪除操作
刪除操作可分為以下幾步:
(1) 判斷插入位置index的合法性.
(2)將第index個(gè)元素的后續(xù)元素前移一位.
(3)將e值插入index位置,并將length減1.
int Delete(SqList &L, int index, DataType &e) {
//index的合法性
//index的范圍是1 <= index <= L.length
if(index < 1 || index > L.length) {
return 0; //刪除失敗,返回0
}
//1.找到要?jiǎng)h除的元素并賦給e
e = L.data[index];
//2.將第index元素的后面的元素前移一位
int i;
for(i = index + 1; i <= L.length; i++) {
L.data[i - 1] = L.data[i];
}
//3.順序表的長(zhǎng)度減1
L.length--;
}
4.定位操作
因?yàn)轫樞虮硎菑南聵?biāo)為1的位置開始存儲(chǔ),所以可以作如下判斷,查找元素值為e的順序表中的元素時(shí),若查找失敗返回0,查找成功返回下標(biāo),成功時(shí)下標(biāo)>0.代碼比較簡(jiǎn)單,如下:
int LocateElem(SqList L, DataType e) {
int i;
for(i = 1; i <= L.length; i++) {
if(L.data[i] == e) {
return i; //查找成功绣否，返回i
}
}
return 0; //若查找失敗，返回0
}
5.遍歷操作
遍歷操作很簡(jiǎn)單,代碼如下:
void Traverse(SqList L) {
for(int i = 1; i <= L.length; i++) {
printf(" %d", L.data[i]);
}
}
6.判斷順序表是否為空
順序表是否為空只需要根據(jù)length的值判斷即可,代碼如下:
int IsEmpty(SqList L){
if(L.length > 0){
return 1;
}
return 0;
}
順序表的實(shí)現(xiàn)算是比較簡(jiǎn)單的.可以加入自動(dòng)增長(zhǎng)順序表空間的功能,只需要判斷是否已經(jīng)滿了,若滿了,只需要另外開辟一個(gè)增長(zhǎng)的空間即可.此時(shí)順序表的結(jié)構(gòu)體需要換成指針式的.具體的代碼,可以見數(shù)據(jù)結(jié)構(gòu)課本.或者下載完整的代碼,我將會(huì)在博客最后貼出.
下面看看鏈表的存儲(chǔ)結(jié)構(gòu)和各種操作實(shí)現(xiàn).
1.5.2 單鏈表
先定義兩個(gè)數(shù)據(jù)類型:
typedef int ElemType; //數(shù)據(jù)類型
typedef int Status; //返回值類型
單鏈表的定義也只有兩個(gè)域,即數(shù)據(jù)域和指針域,數(shù)據(jù)域保存當(dāng)前節(jié)點(diǎn)的數(shù)據(jù),可以多種(代碼為整形變量),指針域保存下一個(gè)節(jié)點(diǎn)的地址.具體代碼如下:
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkedList;
以下是單鏈表的各種操作
1.初始化操作:
初始化操作是生成一個(gè)頭結(jié)點(diǎn),并將頭結(jié)點(diǎn)的next值賦值為NULL即可,代碼如下:
Status Init(LinkedList &head) {
head = (LinkedList) malloc(sizeof(LNode));
if (!head)return ERROR;
head->next = NULL;
return OK;
}
2.插入操作:
插入操作要考慮的因素有以下幾點(diǎn):
(1)插入的位置的合法性
(2)單鏈表因?yàn)槠涮攸c(diǎn),插入操作比較簡(jiǎn)單,只需要修改指針即可,所以難點(diǎn)是在插入位置的判斷上.代碼如下:
Status Insert(LinkedList &L, int i, ElemType e)
LinkedList p = L;
LinkedList s; //待插入節(jié)點(diǎn)
int j = 0; //j=0時(shí),p指向頭結(jié)點(diǎn)
//找到第i個(gè)節(jié)點(diǎn)的位置,循環(huán)結(jié)束之后,p指向第i-1個(gè)元素
while (p && j < i - 1) {
p = p->next;
++j;
}
//若i小于1,或者i大于鏈表長(zhǎng)度+1
//i小于1時(shí),循環(huán)之后j > i - 1
//若i > 長(zhǎng)度+1,那么最后p指向的是NULL,而本應(yīng)該指向的是第i-1個(gè)元素
if (!p || j > i - 1)return ERROR;
//為新節(jié)點(diǎn)開辟內(nèi)存空間
s = (LinkedList) malloc(sizeof(LNode));
//將新元素插入其中
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
3.刪除操作
刪除操作原理同上.需要注意的是,刪除元素的i的范圍不一樣.因?yàn)椴荒軇h除第length+1個(gè)元素,因?yàn)椴淮嬖?
Status Delete(LinkedList &L, int i, ElemType &e) {
LinkedList q, p = L;
int j = 0;
while (p && j < i - 1) {//find the No. i-1 LNode
p = p->next;
++j;
}
if (!p || j > i - 1)return ERROR;
//if L has element[i], p->next is now point to it.
q = p->next;
p->next = q->next;
e = q->data;
free(q);
return OK;
}
4.獲取元素
獲取元素的原理也同上,需要注意的是,同插入不同.獲取元素的范圍和刪除時(shí)一樣.以下代碼因?yàn)閜和j的初始值不一樣,所以后面的判斷也是不一樣的,需要注意.代碼如下:
Status GetElem(LinkedList &L, int i, ElemType &e) {
LinkedList p = L->next; //這里開始指向的是第一個(gè)節(jié)點(diǎn)
int j = 1;//所以j也要相應(yīng)的指向第一個(gè)節(jié)點(diǎn)
while (p && j < i) {
p = p->next;
++j;
}
if (!p || j > i)return ERROR;
e = p->data;
return OK;
}
5.一個(gè)重要但是簡(jiǎn)單的操作就是遍歷操作.代碼如下:
Status Traverse(LinkedList &L) {
int count = 0;
LinkedList p = L->next;
while (p) {
count++;
cout << p->data << " ";
p = p->next;
}
}
6.下面介紹兩個(gè)重要的操作,就是尾插法和頭插法建立單鏈表的操作.
頭插法,即在頭部插入元素,就是每個(gè)元素插入之后,會(huì)在鏈表的第一的位置,所以頭插法建立的單鏈表是倒序的.
頭插法關(guān)鍵步驟:
(1)建立新的節(jié)點(diǎn)保存待插入元素.
(2)將此節(jié)點(diǎn)的指針域(next指針指向頭元素,即第一個(gè)元素,即p->next = head->next;).
(3)將頭指針指向p節(jié)點(diǎn)(新建立的節(jié)點(diǎn)),即head->next = p;.
頭插法代碼如下:
//create a length's LinkedList by head insert method
//this method causes a reversed sequence.
void CreateListHead(LinkedList &L, int length) {
//first, create a null LinkedList with a head node
L = (LinkedList) malloc(sizeof(LNode));
L->next = NULL;
LinkedList p;
//input the array that will be inserted.
cout << "Please enter " << length << " numbers." << endl;
ElemType e[length];
for (int i = 0; i < length; i++) {
cin >> e[i];
}
//create node and insert into head->next
for (int i = 0; i < length; i++) {
p = (LinkedList) malloc(sizeof(LNode));
p->data = e[i];
//insert
p->next = L->next;
L->next = p;
}
}
尾插法和頭插法正好相反,是在尾部插入,順序是正的.
尾插法的關(guān)鍵步驟如下:
(1)建立一個(gè)指向末尾元素的指針,r,初始指向頭結(jié)點(diǎn),隨著元素的插入,每次都指向末尾元素.
(2)建立一個(gè)新的元素p,用于保存插入的元素.
(3)對(duì)p賦值之后接入鏈表末尾,即r->next = p;
(4)更新r的位置,即r = p;.
尾插法的代碼如下,需要注意一些細(xì)節(jié):
//create a length's LinkedList by rear insert method
//this method causes a normal order sequence.
void CreateListRear(LinkedList &L, int length) {
//first, create a null LinkedList with a head node
L = (LinkedList) malloc(sizeof(LNode));
//declare a new LinkedList which point to L(null at first)
//r point to the end of L when inserting.
LinkedList r = L;
//input the array supposed to be inserted.
cout << "Please enter " << length << " numbers." << endl;
ElemType e[length];
for (int i = 0; i < length; i++) {
scanf("%d", &e[i]);
}
LinkedList p;
//create node and insert into head->next
for (int i = 0; i < length; i++) {
p = (LinkedList) malloc(sizeof(LNode));
p->data = e[i];
//insert
r->next = p;
r = p;
}
r->next = NULL;//the pointer of the last elem. must be NULL.
}
1.6 應(yīng)用實(shí)例
至此,順序表的單鏈表的存儲(chǔ)結(jié)構(gòu)和基本操作已經(jīng)整理完畢.下面給出兩個(gè)個(gè)例題,作為操練:
(1)請(qǐng)逆序打印出單鏈表的所有元素,假設(shè)初始時(shí),L指針指向單鏈表的開始節(jié)點(diǎn).
解析:開始時(shí)指向第一個(gè)節(jié)點(diǎn),那么需要逆序打印的話可以考慮用遞歸的方法.參考代碼如下:
void print(LinkedList &L){
if(L != NULL){
print(L->next);
printf("%d ", L->data);
}
}
(2)有一個(gè)int型數(shù)組,里面保存的是個(gè)位數(shù)的int數(shù)據(jù)(即0~9的數(shù)字), N <= 9, 數(shù)組的長(zhǎng)度為N,另給出一個(gè)int i, 不能使用其他變量,設(shè)計(jì)一個(gè)算法,求出數(shù)組中的最小者.
解析:意思是,只能用數(shù)組本身和i變量,求出其最小值.下面給出一個(gè)以前常用的一個(gè)求數(shù)組最小值的算法,如下:
#include <iostream>
#include <stdio.h>
using namespace std;
#define N 10
int main() {
int a[N];
for(int i = 0; i < N; i++) {
scanf("%d", &a[i]);
}
int min1 = a[0];
for(int j = 1; j < N; j++) {
if(a[j] < min1) {
min1 = a[j];
}
}
cout << min1 << endl;
return 0;
}
從以上代碼可以看出,需要找出最小值,必須有一個(gè)保存當(dāng)前循環(huán)的最小值的變量,而題目只給了一個(gè)i,所以i必須分成兩半用.
重新研究題目意思可以知道,數(shù)組保存的數(shù)據(jù)是一個(gè)個(gè)位數(shù),也就是說(shuō)是一個(gè)十位數(shù)是0的數(shù),可以這樣分開i,用i的十位數(shù)保存當(dāng)前的循環(huán),i的個(gè)位數(shù)保存當(dāng)前的最小值,因?yàn)樽钚≈禐閭€(gè)位數(shù),所以i可以完成保存兩個(gè)變量的使命,參考代碼如下,注釋已經(jīng)很詳細(xì)了:
void FindMin(int a[], int &i){
i = a[0]; //初始時(shí)保存第一個(gè)數(shù)
while(i / 10 < N){
//循環(huán)繼續(xù)的條件,初始時(shí)i = a[0],十位為0, 每次循環(huán)之后對(duì)十位加1即可.
if(i % 10 > a[i/10]){
//用i個(gè)位上的數(shù)字,即當(dāng)前最小值,和a中第i/10(i的十位數(shù),即當(dāng)前比較的a數(shù)組元素的下標(biāo))個(gè)數(shù).
//若a[..]更小,則更新i的個(gè)位數(shù)字
i = i - i % 10;
i = i + a[i/10];
}
i += 10;//即十位上數(shù)字加1,進(jìn)入下一個(gè)比較.
}
i = i % 10;//獲取個(gè)位上的數(shù)字,即最小值
}
今天就到這里了,完整的代碼后續(xù)會(huì)更新此到這里.謝謝~~~~
