数据结构之线性表代码

一，顺序表

1.1 顺序表的实现

静态实现：

#define MaxSize 10 // 定义最大长度 

typedef struct {
	int data[MaxSize]; // 使用静态的数组存放数据元素 
	int length; // 顺序表的当前长度 
}SqList;

// 初始化顺序表 
void InitList(SqList &L) {
	L.length = 0; // 顺序表初始长度为0 
}

int main() {
	SqList L; // 声明一个顺序表 
	InitList(L); // 初始化顺序表 
	return 0;
}

动态实现：

#define MaxSize 10 // 定义最大长度 
#define InitSize 10 // 顺序表的初始长度

typedef struct {
	int *data; // 声明动态分配数组的指针 
	int MaxSize; // 顺序表的最大容量
	int length; // 顺序表的当前长度 
}SeqList;

// 初始化顺序表 
void InitList(SqList &L) {
	// 用malloc函数申请一片连续的存储空间 
	L.data = (int *)malloc(InitSize * sizeof(int));
	L.length = 0;
	L.MaxSize = InitSize;
}

// 增加动态数组的长度 
void IncreaseSize(SqList &L, int len) {
	int *p = L.data;
	L.data = (int *)malloc((L.MaxSize+len) * sizeof(int));
	for (int i = 0; i < L.length; i++)
		L.data[i] = p[i]; // 将数据复制到新区域 
	L.MaxSize = L.MaxSize + len; // 顺序表最大长度增加len 
	free(p); // 释放原来的内存空间 
}

int main() {
	SeqList L; // 声明一个顺序表 
	InitList(L); // 初始化顺序表 
    ...
	IncreaseSize(L, 5);
	return 0;
}

malloc() 函数的作用：会申请一片存储空间，并返回存储空间第一个位置的地址，也就是该位置的指针。

1.2 顺序表的基本操作

插入：

// 在顺序表i位置插入e
bool ListInsert(SqList &L, int i, int e) {
	if (i < 1 || i > L.length+1) // 判断i的范围是否有效 
		return false;
	if (L.length >= MaxSize) // 判断存储空间是否已满 
		return false;
	for (int j = L.length; j >= i; j--) // 将第i个元素之后的元素后移 
		L.data[j] = L.data[j-1];
	L.data[i-1] = e; // 在位置i处放入e 
	L.length++; // 长度+1 
	return true;
}

时间复杂度：

最好时间复杂度：O ( 1 )
最坏时间复杂度：O ( n )
平均时间复杂度：O ( n )

删除：

// 删除顺序表i位置的数据并存入e
bool ListDelete(SqList &L, int i, int &e) {
	if (i < 1 || i > L.length) // 判断i的范围是否有效
		return false;
	e = L.data[i-1]; // 将被删除的元素赋值给e 
	for (int j = i; j < L.length; j++) //将第i个位置后的元素前移 
		L.data[j-1] = L.data[j];
	L.length--;
	return true; 
}

时间复杂度：

最好时间复杂度：O ( 1 )
最坏时间复杂度：O ( n )
平均时间复杂度：O ( n )

按位查找：

// 静态分配的按位查找
#define MaxSize 10

ElemType GetElem(SqList L, int i) {
	return L.data[i-1];
}

// 动态分配的按位查找
#define InitSize 10

ElemType GetElem(SeqList L, int i) {
	return L.data[i-1];
}

时间复杂度： O ( 1 )

按值查找：

// 查找第一个元素值为e的元素，并返回其位序 
int LocateElem(SqList L, ElemType e) {
	for (int i = 0; i < L.length; i++)
		if (L.data[i] == e)
			return i+1; // 数组下标为i的元素值等于e，返回其位序i+1 
	return 0; // 没有查找到 
}

在《数据结构》考研初试中，手写代码可以直接用“==”，无论 ElemType 是基本数据类型还是结构类型

时间复杂度：

最好时间复杂度：O ( 1 )
最坏时间复杂度：O ( n )
平均时间复杂度：O ( n )

二，单链表

2.1 单链表的实现

不带头结点的单链表：

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

//初始化一个空的单链表
bool InitList(LinkList &L){
    L = NULL;//空表，暂时还没有任何结点
    return true;
}

void test(){
    LinkList L;//声明一个指向单链表的头指针
    //初始化一个空表
    InitList(L);
    ...
}

//判断单链表是否为空
bool Empty(LinkList L){
    return (L==NULL)
}

带头结点的单链表：

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

// 初始化一个单链表（带头结点）
bool InitList(LinkList &L){
    L = (LNode *)malloc(sizeof(LNode));//分配一个头结点
    if (L == NULL)//内存不足，分配失败
    	return false;
    L->next = NULL;//头结点之后暂时还没有结点
    return true;
}

void test(){
    LinkList L;//声明一个指向单链表的头指针
    //初始化一个空表
    InitList(L);
    ...
}

//判断单链表是否为空
bool Empty(LinkList L){
    if (L->next == NULL)
        return true;
    else
        return false;
}

2.2 单链表的建立

尾插法建立单链表：

// 使用尾插法建立单链表L
LinkList List_TailInsert(LinkList &L){
    int x;//设ElemType为整型int
    L = (LinkList)malloc(sizeof(LNode));//建立头结点(初始化空表)
    LNode *s, *r = L;//r为表尾指针
    scanf("%d", &x);//输入要插入的结点的值
    while(x!=9999){//输入9999表示结束
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;//r指针指向新的表尾结点
        scanf("%d", &x);
    }
    r->next = NULL;//尾结点指针置空
    return L;
}

时间复杂度：O ( n )

头插法建立单链表：

LinkList List_HeadInsert(LinkList &L){//逆向建立单链表
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));//建立头结点
    L->next = NULL;//初始为空链表,这步很关键
    scanf("%d", &x);//输入要插入的结点的值
    while(x!=9999){//输入9999表结束
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
		//将新结点插入表中，L为头指针
		scanf("%d", &x);
    }
    return L;
}

头插法实现链表的逆置：

// 将链表L中的数据逆置并返回
LNode *Inverse(LNode *L){
    LNode *p, *q;
    p = L->next;//p指针指向第一个结点
    L->next = NULL;//头结点置空
    // 依次判断p结点中的数据并采用头插法插到L链表中
    while (p != NULL){
        q = p;
        p = p->next;
        q->next = L->next;
        L->next = q;
    }
    return L;
}

2.3 单链表的基本操作

按位序插入（带头结点）：

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

//在第i个位置插入元素e
bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1)
        return False;
    LNode *p; //指针p指向当前扫描到的结点
    int j=0;  //当前p指向的是第几个结点
    p = L;    //循环找到第i-1个结点
    while(p!=NULL && j<i-1){ //如果i>lengh，p最后会等于NULL
        p = p->next;
        j++;
    }
	//p值为NULL说明i值不合法
    if (p==NULL)
        return false;
	//在第i-1个结点后插入新结点
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
	//将结点s连到p后
    return true;
}

时间复杂度：

最好时间复杂度：O ( 1 )
最坏时间复杂度：O ( n )
平均时间复杂度：O ( n )

按位序插入（不带头结点）：

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

//在第i个位置插入元素e
bool ListInsert(LinkList &L, int i, ElemType e){
	//判断i的合法性
    if(i<1)
        return false;
	//需要判断插入的位置是否是第1个
    if(i==1){
        LNode *s = (LNode *)malloc(size of(LNode));
        s->data =e;
        s->next =L;
        L=s;//头指针指向新结点
        return true;
    }
	//i>1的情况与带头结点一样，唯一区别是j的初始值为1
    LNode *p;//指针p指向当前扫描到的结点
    int j=1;//当前p指向的是第几个结点
    p = L;
	//循环找到第i-1个结点
    while(p!=NULL && j<i-1){//如果i>lengh，p最后会等于NULL
        p = p->next;
        j++;
    }
	//p值为NULL说明i值不合法
    if (p==NULL)
        return false;
	//在第i-1个结点后插入新结点
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

时间复杂度：

最好时间复杂度：O ( 1 )
最坏时间复杂度：O ( n )
平均时间复杂度：O ( n )

除非特别声明，否则之后的代码都默认为带头结点

指定结点的后插操作：

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

// 在结点p后插入元素e
bool InsertNextNode(LNode *p, ElemType e){
    if(p==NULL){
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if(s==NULL)
        return false;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

// 按位序插入的函数中可以直接调用后插操作
bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1)
        return False;
    LNode *p;
	//指针p指向当前扫描到的结点
	int j=0;
	//当前p指向的是第几个结点
    p = L;
	//循环找到第i-1个结点
    while(p!=NULL && j<i-1){
	//如果i>lengh, p最后会等于NULL
        p = p->next;
        j++;
    }
    return InsertNextNode(p, e)
}

时间复杂度：O ( 1 )

指定结点的前插操作：

如果传入头指针，就可以循环整个链表找到指定结点p的前驱结点q，再对q进行后插操作；
如果不传入头指针，可以在指定结点p后插入一个结点s，并交换两个结点所保存的数据，从而变相实现指定结点的前插操作。

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

// 在结点p前插入元素e
bool InsertPriorNode(LNode *p, ElemType e){
    if(p==NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
	// 内存不足分配失败
	if(s==NULL)
        return false;
	// 将s插入结点p之后
    s->next = p->next;
    p->next = s;
	// 交换两个结点中的数据
    s->data = p->data;
    p->data = e;
    return true;
}

时间复杂度：O ( 1 )

按位序删除：

typedef struct LNode{
    ElemType data;
    struct LNode *next;}LNode, *LinkList;

// 删除第i个结点并将其所保存的数据存入e
bool ListDelete(LinkList &L, int i, ElemType &e){
    if(i<1)
        return false;
    LNode *p;//指针p指向当前扫描到的结点
    int j=0;//当前p指向的是第几个结点
    p = L;
	//循环找到第i-1个结点
    while(p!=NULL && j<i-1){
	//如果i>lengh，p和p的后继结点会等于NULL
        p = p->next;
        j++;
    }
    if(p==NULL)
        return false;
    if(p->next == NULL)
        return false;
//令q暂时保存被删除的结点
    LNode *q = p->next;
    e = q->data;
    p->next = q->next;
    free(q)
    return true;
}

时间复杂度：

最好时间复杂度：O ( 1 )
最坏时间复杂度：O ( n )
平均时间复杂度：O ( n )

删除指定结点：

如果传入头指针，就可以循环整个链表找到指定结点p的前驱结点q，再对p进行删除操作；
如果不传入头指针，可以把指定结点p的后继结点q删除，并使结点p保存结点q存储的数据，从而变相实现删除指定结点的操作。但是如果指定结点p没有后继结点，这么做会报错。

// 删除指定结点p
bool DeleteNode(LNode *p){
    if(p==NULL)
        return false;
    LNode *q = p->next;// 令q指向p的后继结点// 如果p是最后一个结点，则q指向NULL，继续执行就会报错
    p->data = q->data;
    p->next = q->next;
    free(q);
    return true;
}

时间复杂度：O ( 1 )

按位查找：

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

// 查找指定位序i的结点并返回
LNode * GetElem(LinkList L, int i){
    if(i<0)
        return NULL;
    LNode *p;
    int j=0;
    p = L;
    while(p!=NULL && j<i){
        p = p->next;
        j++;
    }
    return p;
}

// 封装后的插入操作，在第i个位置插入元素e，可以调用查询操作和后插操作
bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1)
        return False;
	// 找到第i-1个元素
    LNode *p = GetElem(L, i-1);
	// 在p结点后插入元素e
	return InsertNextNode(p, e)
}

时间复杂度：

最好时间复杂度：O ( 1 )
最坏时间复杂度：O ( n )
平均时间复杂度：O ( n )

按值查找：

// 查找数据域为e的结点指针，否则返回NULL
LNode * LocateElem(LinkList L, ElemType e){
    LNode *P = L->next;
    // 从第一个结点开始查找数据域为e的结点
    while(p!=NULL && p->data != e){
        p = p->next;
    }
    return p;
}

时间复杂度：

最好时间复杂度：O ( 1 )
最坏时间复杂度：O ( n )
平均时间复杂度：O ( n )

计算单链表长度：

// 计算单链表的长度
int Length(LinkList L){
    int len=0;//统计表长
    LNode *p = L;
    while(p->next != NULL){
        p = p->next;
        len++;
    }
    return len;
}

时间复杂度：O ( n )

三，双链表

双链表的初始化 (带头结点)

typedef struct DNode{            //定义双链表结点类型
    ElemType data;               //数据域
    struct DNode *prior, *next;  //前驱和后继指针
}DNode, *DLinklist;

// 初始化双链表
bool InitDLinkList(Dlinklist &L){
    L = (DNode *)malloc(sizeof(DNode));
    if(L==NULL)
        return false;
    L->prior = NULL;//头结点的prior指针永远指向NULL
    L->next = NULL;//头结点之后暂时还没有结点，置空
    return true;
}

void testDLinkList(){
    DLinklist L;
    InitDLinkList(L);
    ...
}

// 判断双链表是否为空
bool Empty(DLinklist L){
    if(L->next == NULL)
        return true;
    else
        return false;
}

双链表的后插操作

typedef struct DNode{
    ElemType data;
    struct DNode *prior, *next;
}DNode, *DLinklist;

// 将结点s插入到结点p之后
bool InsertNextDNode(DNode *p, DNode *s){ 
    if(p==NULL || s==NULL)  
        return false;         
    s->next = p->next;      
    // 判断结点p之后是否有后继结点  
    if (p->next != NULL)   
        p->next->prior = s; 
    s->prior = p;   
    p->next = s;     
    return true;
}

双链表的前插操作、按位序插入操作都可以转换成后插操作

双链表的删除操作

// 删除p结点的后继结点
bool DeletNextDNode(DNode *p){   
    if(p==NULL)           
        return false;   
    // 找到p的后继结点q    
    DNode *q =p->next;   
    if(q==NULL)          
        return false;    
    p->next = q->next;   
    if(q->next != NULL) 
        q->next->prior=p;  
    free(q);     
    return true;
}

// 销毁一个双链表
bool DestoryList(DLinklist &L){ 
    // 循环释放各个数据结点   
    while(L->next != NULL){    
        DeletNextDNode(L);      
        free(L);        
        // 头指针置空  
        L=NULL;     
    }
}

双链表的遍历

// 向后遍历
while(p!=NULL){    
    // 对结点p做相应处理    
    p = p->next;
}

// 向前遍历
while(p!=NULL){    
    // 对结点p做相应处理 
    p = p->prior;
}

// 跳过头结点的遍历
while(p->prior!=NULL){ 
    //对结点p做相应处理    
    p = p->prior;
}

双链表不可随机存取，按位查找、按值查找操作都只能用遍历的方式实现。

四，循环链表

循环单链表的实现

typedef struct LNode{           
    ElemType data;                  
    struct LNode *next; 
}DNode, *Linklist;

// 初始化循环单链表
bool InitList(LinkList &L){    
    L = (LNode *)malloc(sizeof(LNode));  
    if(L==NULL)             
        return false;    
    // 最后一个结点的next指针指向头结点    
    L->next = L;       
    return true;
}

// 判断循环单链表是否为空
bool Empty(LinkList L){    
    if(L->next == L)       
        return true;    
    else             
        return false;
}

// 判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L, LNode *p){ 
    if(p->next == L)          
        return true;      
    else            
        return false;
}

循环双链表的实现

typedef struct DNode{            
    ElemType data;           
    struct DNode *prior, *next;  
}DNode, *DLinklist;

// 初始循环双链表
bool InitDLinkList(DLinklist &L){  
    L = (DNode *) malloc(sizeof(DNode));  
    if(L==NULL)            
        return false;    
    // 头结点的prior指针指向最后一个结点，最后一个结点的next指针指向头结点 
    L->prior = L;      
    L->next = L;
}

// 判断循环双链表是否为空
bool Empty(DLinklist L){   
    if(L->next == L)       
        return true;      
    else           
        return false;
}

// 判断结点p是否为循环双链表的表尾结点
bool isTail(DLinklist L, DNode *p){   
    if(p->next == L)        
        return true;     
    else            
        return false;
}

循环双链表的插入和删除操作

// 将结点s插入到结点p之后
bool InsertNextDNode(DNode *p, DNode *s){  
    s->next = p->next;   
    //循环双链表不用担心p结点的下一个结点为空   
    p->next->prior = s;  
    s->prior = p;     
    p->next = s;
}

// 删除p结点的后继结点
bool DeletNextDNode(DNode *p){  
    // 找到p的后继结点q       
    DNode *q =p->next;        
    //循环双链表不用担心q结点的下一个结点为空  
    p->next = q->next;    
    q->next->prior=p;    
    free(q);      
    return true;
}

参考自：https://blog.csdn.net/qq_55593227/article/details/123598044

考研408

数据结构之线性表代码

https://jimes.cn/2024/02/02/structure of data of list/

作者

Jimes

发布于

2024年2月2日

许可协议

数据结构之栈与队列代码上一篇

python程序带图片等资源打包下一篇