線性表
線性表概念
線性表定義:具有相同特性數(shù)據(jù)元素的有限序列。
線性表的邏輯結(jié)構(gòu):線性結(jié)構(gòu)。只有一個(gè)表頭，只有一個(gè)表尾。表頭元素沒有前驅(qū)，表尾元素沒有后繼。其余都有一個(gè)直接前驅(qū)與后繼。
線性表的物理結(jié)構(gòu):順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
- 順序表:將元素按照其邏輯順序，依次存儲(chǔ)在指定位置開始的一片連續(xù)的存儲(chǔ)空間中。
- 鏈表：在內(nèi)存中可以不連續(xù)。每個(gè)結(jié)點(diǎn)中不止包括所存元素的信息，還有元素之間邏輯關(guān)系的信息。如單鏈表中后繼結(jié)點(diǎn)。
兩種儲(chǔ)存結(jié)構(gòu)的比較：
順序表:
- 隨機(jī)訪問性 (知道0點(diǎn)位置。就可以在o（1）時(shí)間找到想要的元素)
- 占用連續(xù)的存儲(chǔ)空間
- 靜態(tài)分配:一旦分配好，操作過程中不會(huì)發(fā)生改變
- 做操作需要移動(dòng)多個(gè)元素
鏈表:
1.不支持隨機(jī)訪問（必須遍歷）
2.結(jié)存的存儲(chǔ)空間利用率較順序表較低（多了結(jié)點(diǎn)邏輯信息）
3.動(dòng)態(tài)分配
4.做操作無須移動(dòng)元素
鏈表的五種形式
1.單鏈表
此處輸入圖片的描述
帶頭結(jié)點(diǎn) ：head->始終不為空，head->next為NULL時(shí)為空鏈表
不帶頭結(jié)點(diǎn):head為NUll時(shí)是空鏈表
帶頭結(jié)點(diǎn)的單鏈表的優(yōu)點(diǎn):
在鏈表第一個(gè)位置上進(jìn)行的操作（插入、刪除）和其它位置上的操作一致,無須進(jìn)行特殊處理;
無論鏈表是否為空，head一定不為空，這使得空表和非空表的處理一致。
2.雙鏈表
此處輸入圖片的描述
比單鏈表在結(jié)點(diǎn)上多了個(gè)前驅(qū)結(jié)點(diǎn)。使得可以從后向前訪問。
3.循環(huán)單鏈表
此處輸入圖片的描述
最后一個(gè)指針域指向開始結(jié)點(diǎn)。
可以做到從任何一個(gè)結(jié)點(diǎn)出發(fā)，訪問任何一個(gè)結(jié)點(diǎn)。
空鏈表:head = head->next
4.循環(huán)雙鏈表
此處輸入圖片的描述
空鏈表：head = head->next或head = head->prior
5.靜態(tài)鏈表
此處輸入圖片的描述
順序表
順序表基本操作:
初始化
插入
刪除
查找
打印
求指定位置元素
代碼:
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
int data[100];
int length;
}sqList;//順序表的結(jié)構(gòu)體定義
/**順序表操作**/
//查找
int findElem(sqList L,int x)//查找
{
for(int i = 0;i<L.length;++i)
{
if(x == L.data[i])
return i;
}
return -1;
}
//插入
int insertElem(sqList *L,int p,int x)
{
int i;
if(p<0||p>L->length||L->length == 100)//順序表超過最大允許值
return 0;
for(i = L->length -1;i>=p;--i)
L->data[i+1]=L->data[i];
L->data[p] = x;
++(L->length);
return 1;
}
//刪除
int deleteElem(sqList *L,int p ,int *x)//將被刪除的元素賦值給x，可以不要這個(gè)步驟
{
int i;
if(p<0||p>L->length-1)
return 0;
*x = L->data[p];
for(i = p;i<L->length-1;++i)
L->data[i]=L->data[i+1];
--(L->length);
return 1;
}
//初始化
void initList(sqList *L)
{
L->length = 0;
}
//求指定位置元素
int getElem(sqList L,int p,int *x)
{
if(p<0||p>L.length-1)
return 0;
*x =L.data[p];
return 1;
}
//打印
void printList(sqList L)
{
for(int i =0;i<L.length;++i)
printf("%d ",L.data[i]);
}
int main()
{
sqList A;
int x=0;
initList(&A);
insertElem(&A,0,1);
insertElem(&A,1,2);
insertElem(&A,1,3);
printf("before delete:\n",x);
printList(A);
deleteElem(&A,1,&x);
printf("\n after delete:\n",x);
printList(A);
printf("刪除的值是%d\n",x);
getElem(A,1,&x);
printf("取的值是%d\n",x);
printf("元素位置是%d\n",findElem(A,1));
return 0;
}
/**
輸出如下
before delete:
1 3 2
after delete:
1 2 刪除的值是3
取的值是2
元素位置是0
**/
單鏈表
單鏈表基本操作:
創(chuàng)建鏈表
插入鏈表（頭、尾插法）
刪除鏈表
打印鏈表
查找鏈表
代碼實(shí)現(xiàn):
//------------單鏈表-------------------
//單鏈表結(jié)點(diǎn)定義
typedef struct lNode
{
int data;
struct lNode *next;//在此語句時(shí)lNode別名還未生效,所以需要用struct lNode來聲明結(jié)構(gòu)體變量
}lNode;
//創(chuàng)建表頭
void createListR(lNode **c)
{
(*c) =(lNode*)malloc(sizeof(lNode));
(*c)->next=NULL;
}
//尾插入
lNode *r = NULL;//全局變量尾指針
void insertLnodeR(lNode **c,int data)
{
lNode *s;
if(r==NULL)
r = (*c);
s = (lNode*)malloc(sizeof(lNode));
s->data = data;
r->next=s;
r=r->next;
r->next=NULL;
}
//打印鏈表
void printListLnode(lNode *headNode)
{
lNode* pMove = headNode->next;
printf("數(shù)據(jù)如下:\n");
while(pMove)
{
printf("%d\n",pMove->data);
pMove = pMove->next;
}
}
//刪除鏈表
void deleteLNode(lNode **c,int x)
{
lNode *p,*pf;
p = (*c)->next;
pf =(*c);//指向頭指針
if(p == NULL)
printf("無法刪除鏈表為空");
while(p->data != x)//如果不為x，使指向前驅(qū)結(jié)點(diǎn)的pf和該節(jié)點(diǎn)p指針向后移動(dòng)
{
pf = p;
p = p->next;
if(p == NULL)
{
printf("沒有找到相關(guān)信息\n");
return;
}
}
pf->next = p->next;//將p結(jié)點(diǎn)從鏈表中移除
free(p);//釋放p結(jié)點(diǎn)空間
int main()
{
lNode *c;
createListR(&c);//以地址的地址為參數(shù)，需要取指針的地址(&c)，而不是指針(c)
insertLnodeR(&c,2);
insertLnodeR(&c,3);
printListLnode(c);
deleteLNode(&c,3);
printListLnode(c);
return 0;
}
}
