首页 > 其他分享 >第2章-线性表

第2章-线性表

时间：2023-06-08 20:13:06浏览次数：23  
标签：结点 return LNode int next data 线性表

1.顺序表

1.1 顺序表的定义

1.1.1 静态分配：

#include<stdio.h>
#define MaxSize 10
typedef struct{
	int data[MaxSize];
	int length;
}Sqlist;
//初始化一个顺序表
void InitList(Sqlist &L){
	for(int i=0;i<MaxSize;i++){
		//TODO
		L.data[i]=0;//将所有数据元素设置为默认初始值
	}
	L.length=0;//顺序表初始长度为0
}
int main()
{
	Sqlist L;//声明一个顺序表
	InitList(L);
	for(int i=0;i<MaxSize;i++)
	{
		printf("data[%d]:%d\n",i,L.data[i]);
	}
	return 0;
}

如果不将所有数据元素设置为默认初始值的话，数组元素中就会有各种奇奇怪怪的数据，这是因为内存中会有遗留的“脏数据”

1.1.2 动态分配：

#include<stdio.h>
#include<stdlib.h>
#define InitSize 10//默认的最大长度
typedef struct{
	int *data;//指示动态分配数组的指针
	int MaxSize;//顺序表的最大容量
	int length;//顺序表的当前长度
}Seqlist;
void InitList(Seqlist &L)
{
    //用malloc函数申请一片连续的存储空间
	L.data=(int *)malloc(InitSize*sizeof(int));
	L.length=0;
	L.MaxSize=InitSize;
}
//增加动态数组的长度
void IncreaseSize(Seqlist &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;
	free(p);
}
int main()
{
	Seqlist L;//声明一个顺序表
	InitList(L);//初始化顺序表
	IncreaseSize(L,5);
	return 0;
}

1.2 顺序表上的基本操作

1.2.1 插入操作

#include<stdio.h>
#define MaxSize 10
typedef struct{
	int data[MaxSize];
	int length;
}Sqlist;
//初始化一个顺序表
void InitList(Sqlist &L){
	for(int i=0;i<MaxSize;i++){
		//TODO
		L.data[i]=0;//将所有数据元素设置为默认初始值
	}
	L.length=0;//顺序表初始长度为0
}
bool ListInsert(Sqlist &L,int i,int e)
{
	if(i<1||i>L.length+1) return false;//判断i的范围是否有效
	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++;//长度加一
	return true;
}
int main()
{
	Sqlist L;//声明一个顺序表
	InitList(L);
	L.data[0]=0,L.length++;
	L.data[1]=1,L.length++;
	L.data[2]=2,L.length++;
	ListInsert(L,2,3);
	for(int i=0;i<L.length;i++)
	{
		printf("data[%d]:%d\n",i,L.data[i]);
	}
	return 0;
}

1.2.2 删除操作

#include<stdio.h>
#define MaxSize 10
typedef struct{
	int data[MaxSize];
	int length;
}Sqlist;
//初始化一个顺序表
void InitList(Sqlist &L){
	for(int i=0;i<MaxSize;i++){
		//TODO
		L.data[i]=0;//将所有数据元素设置为默认初始值
	}
	L.length=0;//顺序表初始长度为0
}
bool ListDelete(Sqlist &L,int i,int &e)
{
	if(i<1||i>L.length+1) return false;//判断i的范围是否有效
	e=L.data[i-1];
	for(int j=i;j<L.length;j++)//将第i个元素之后的元素前移
	{
		L.data[j-1]=L.data[j];
	}
	L.length--;//长度减一
	return true;
}
int main()
{
	Sqlist L;//声明一个顺序表
	InitList(L);
	int e=-1;
	L.data[0]=0,L.length++;
	L.data[1]=1,L.length++;
	L.data[2]=2,L.length++;
	L.data[3]=3,L.length++;
	if(ListDelete(L,3,e))
		printf("被删除的元素为%d\n",e);
	else
		printf("位序i不合法，删除失败\n");
	for(int i=0;i<L.length;i++)
	{
		printf("data[%d]:%d\n",i,L.data[i]);
	}	
	return 0;
}

1.2.3 查找操作

按位查找

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

按值查找

#include<stdio.h>
#include<stdlib.h>
#define InitSize 10//默认的最大长度
typedef struct{
	int *data;//指示动态分配数组的指针
	int MaxSize;//顺序表的最大容量
	int length;//顺序表的当前长度
}Seqlist;
void InitList(Seqlist &L)
{
    //用malloc函数申请一片连续的存储空间
	L.data=(int *)malloc(InitSize*sizeof(int));
	L.length=0;
	L.MaxSize=InitSize;
}
//增加动态数组的长度
void IncreaseSize(Seqlist &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;
	free(p);
}
int LocateElem(Seqlist L,int e)
{
	for(int i=0;i<L.length;i++)
	{
		if(L.data[i]==e)
			return i+1;
	}
	return 0;
}
int main()
{
	Seqlist L;//声明一个顺序表
	InitList(L);//初始化顺序表
	//IncreaseSize(L,5);
	L.data[0]=1,L.length++;
	L.data[1]=2,L.length++;
	L.data[2]=3,L.length++;
//	for(int i=0;i<L.length;i++){
//		//TODO
//		printf("L%d:%d\n",i,L.data[i]);
//	}
	printf("%d",LocateElem(L,2));
	return 0;
}

2.链表

2.1单链表

2.1.1单链表的定义

struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;
typedef struct LNode LNode;
typedef	struct LNode *LinkList;//用LinkList表示这是一个指向LNode类型的指针

更简介的写法：

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

强调这是一个单链表 --使用LinkList

强调这是一个结点 --使用LNode *

不带头结点的单链表

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;
bool InitList(LinkList &L)
{
	L=NULL;
	return true;
}
//bool Empty(LinkList L)
//{
//	if(L==NULL) return true;
//	else return false;
//}
bool empty(LinkList L)
{
	return (L==NULL);
}
int main()
{
	LinkList L;
	InitList(L);	
	return 0;
}

带头结点的单链表

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode{//定义单链表结点类型
	int 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;
}

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

int main()
{
	LinkList L;//声明一个指向单链表的指针
	InitList(L);//初始化一个空表
	return 0;
}

2.1.2单链表的插入

2.1.2.1按位序插入

在第i个位置插入元素e（带头结点）

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

bool ListInsert(LinkList &L,int i,ElemType e)
{
    if(i<1) //位序肯定是大于等于1的
        return false;
    LNode *p; //指针p指向当前扫描到的结点
    int j=0; //j用来表示当前p指向的是第几个结点
    p=L; //刚开始先指向头结点，头结点是第0个结点（一般不存数据）
    while(p!=NULL && j<i-1) //用一个while循环找到第i-1个结点
    {
        p=p->next;
        j++;
    }
    if(p==NULL) //i值不合法（如果插入的位置比总结点个数还大1的话）
        return false;
    LNode *s=(LNode *)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next; //把p的后继结点变成s的后继结点
    p->next=s;	//p的后继结点变成s
    return true;//插入成功
}

平均时间复杂度O(n)

不带头结点

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

bool ListInsert(LinkList &L,int i,ElemType e)
{
    if(i<1) //位序肯定是大于等于1的
        return false;
    if(i==1)	//插入第一个结点时与其他结点不同
    {
        LNode *s=(LNode *)malloc(sizeof(LNode));
        s->data=e;
        s->next=L;
        L=s;	//把头指针指向新结点
        return true;
    }
    LNode *p; //指针p指向当前扫描到的结点
    int j=1; //j用来表示当前p指向的是第几个结点
    p=L; //指向第1个结点（此时就不是头结点了）
    while(p!=NULL && j<i-1) //用一个while循环找到第i-1个结点
    {
        p=p->next;
        j++;
    }
    if(p==NULL) //i值不合法（如果插入的位置比总结点个数还大一的话）
        return false;
    LNode *s=(LNode *)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next; //把p的后继结点变成s的后继结点
    p->next=s;	//p的后继结点变成s
    return true;//插入成功
}
2.1.2.2指定结点的后插操作
//后插操作，在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;	//写入数据元素e
    s->next=p->next;
    p->next=s;	//将s连到p之后
    return true;
}

时间复杂度为O（1）

前面的插入函数就可以改成：

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

bool ListInsert(LinkList &L,int i,ElemType e)
{
    if(i<1) //位序肯定是大于等于1的
        return false;
    LNode *p; //指针p指向当前扫描到的结点
    int j=0; //j用来表示当前p指向的是第几个结点
    p=L; //刚开始先指向头结点，头结点是第0个结点（一般不存数据）
    while(p!=NULL && j<i-1) //用一个while循环找到第i-1个结点
    {
        p=p->next;
        j++;
    }
  	return InsertNextNode(p,e);
}
2.1.2.3指定结点的前插操作

其实本质上还是后插操作，只是把原来前面结点的数据复制到后面的结点上，再把新的数据放到前面这个结点上，看起来就像前插操作。

bool InsertPriorLNode(LNode *p,ElemType e)
{
    if(p==NULL) return false;
    LNode *s=(LNode *)malloc(sizeof(LNode));
    if(s==NULL) return false;	//内存分配失败
    s->next=p->next;
    p->next=s;	//新结点s放到p之后
    s->data=p->data;	//将p中元素复制到s中
    p->data=e;		//将新元素e放到p中，类似于前插操作
    return true;
}

bool InsertPriorLNode(LNode *p,LNode *s)
{
    if(p==NULL || s==NULL) return false;
    s->next=p->next;
    p->next=s;
    ELemType temp=p->data;	//设置一个临时变量存储p的数据
    p->data=s->data;
    s->data=temp;
    return true;
}

2.1.3单链表的删除操作

2.1.3.1按位序删除
typedef struct LNode
{
    ELemType data;
    struct LNode *next;
}LNode,*LinkList;

bool ListDelete(LinkList &L,int i,ElemType &e)
{
    if(i<1) //位序肯定是大于等于1的
        return false;
    LNode *p; //指针p指向当前扫描到的结点
    int j=0; //j用来表示当前p指向的是第几个结点
    p=L; //刚开始先指向头结点，头结点是第0个结点（一般不存数据）
    while(p!=NULL && j<i-1) //用一个while循环找到第i-1个结点
    {
        p=p->next;
        j++;
    }
    if(p==NULL) 
        return false;
    if(p->next==NULL) //第i-1个结点之后已经没有结点
        return false;
    LNode *q=p->next;	//让q指向要被删除的结点
    p->next=q->next;	//将*q结点从链中断开
    e=q->data;			//用e返回元素的值
    free(q);		//释放结点的存储空间
    return true;//删除成功
}
2.1.3.2删除指定结点
//删除指定结点p
bool DeleteNode(LNode *p)
{
    if(p==NULL) return false;
    LNode *q=p->next;		//令q指向*p的后继结点
    p->data=p->next->data;	//和后继结点交换数据
    p->next=q->next;		//将*q从链中断开
    free(q);				//释放后继结点的存储空间
    return true;
}

2.1.4单链表的查找

2.1.4.1按位查找
//按位查找，返回第i个元素（带头结点）
LNode *GetElem(LinkList L,int i)
{
	if(i<0) return NULL;
    LNode *p;	//指针p指向当前扫描到的结点
    int j=0;	//j表示当前p指向的是哪个结点
    p=L;		//L指向头结点，头结点是第0个结点
    while(p!=NULL && j<i)	//循环找到第i个结点
    {
        p=p->next;
        j++;
	}
    return p;
}

LNode *GetElem(LinkList L,int i)
{
	int j=1;//表示指针p刚开始在第一个结点
    LNode *p=L->next;
    if(i==0) return L;
    if(i<1) return NULL;
    while(p!=NULL && j<i)
    {
        p=p->next;
        j++;
	}
    return p;
}

所以前面的插入还有删除函数都可以改成：

bool ListInsert(LinkList &L,int i,ElemType e)
{
    if(i<1) //位序肯定是大于等于1的
        return false;
    LNode *p=GetElem(L,i-1);
  	return InsertNextNode(p,e);
}
2.1.4.2按值查找
//按值查找，找到数据元素==e的结点
LNode *LocateElem(LinkList L,ElemType e)
{
    LNode *p=L->next;
    //从第一个结点开始查找数据为e的结点
    while(p!=NULL && p->data!=e)
    {
        p=p->next;
    }
    return p;//找到后返回该结点指针，否则返回NULL
}

2.1.5求单链表的长度

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

2.1.6单链表的建立

2.1.6.1 尾插法建立单链表
LinkList List_TailInsert(LinkList &L)
{
	int x;
	L=(LNode *)malloc(sizeof(LNode));
	LNode *s;
	LNode *r=L;
	scanf("%d",&x);
	while(x!=9999)
	{
		s=(LNode *)malloc(sizeof(LNode));
		s->data=x;
		r->next=s;
		r=s;
		scanf("%d",&x);
	}
	r->next=NULL;
	return L;
}
2.1.6.2 头插法建立单链表
LinkList List_HeadInsert(LinkList &L)
{
	LNode *s;
	int x;
	L=(LinkList)malloc(sizeof(LNode));
	L->next=NULL;						//初始为空链表
	scanf("%d",&x);						//输入结点的值
	while(x!=9999)
	{
		s=(LNode*)malloc(sizeof(LNode));//创建新结点
		s->data=x;
		s->next=L->next;
		L->next=s;						//将新结点插入表中，L为头指针
		scanf("%d",&x);
	}
	return L;
}

重要应用：链表的逆置

2.1.7 单链表实验程序

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode{
	int 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;
}

bool Empty(LinkList L)
{
	if(L->next==NULL) return true;
	else return false;
}
//bool ListInsert(LinkList &L,int i,int e)
//{
//    if(i<1) //位序肯定是大于等于1的
//        return false;
//    if(i==1)	//插入第一个结点时与其他结点不同
//    {
//        LNode *s=(LNode *)malloc(sizeof(LNode));
//        s->data=e;
//        s->next=L;
//        L=s;	//把头指针指向新结点
//        return true;
//    }
//    LNode *p; //指针p指向当前扫描到的结点
//    int j=1; //j用来表示当前p指向的是第几个结点
//    p=L; //指向第1个结点（此时就不是头结点了）
//    while(p!=NULL && j<i-1) //用一个while循环找到第i-1个结点
//    {
//        p=p->next;
//        j++;
//    }
//    if(p==NULL) //i值不合法（如果插入的位置比总结点个数还大一的话）
//        return false;
//    LNode *s=(LNode *)malloc(sizeof(LNode));
//    s->data=e;
//    s->next=p->next; //把p的后继结点变成s的后继结点
//    p->next=s;	//p的后继结点变成s
//    return true;//插入成功
//}

//后插操作，在p结点之后插入元素e
bool InsertNextNode(LNode *p,int e) 
{
    if(p==NULL) return false;
    LNode *s=(LNode *)malloc(sizeof(LNode));
    if(s==NULL)	//内存分配失败
        return false;
    s->data=e;	//写入数据元素e
    s->next=p->next;
    p->next=s;	//将s连到p之后
    return true;
}

//bool ListInsert(LinkList &L,int i,int e)
//{
//    if(i<1) //位序肯定是大于等于1的
//        return false;
//    LNode *p; //指针p指向当前扫描到的结点
//    int j=0; //j用来表示当前p指向的是第几个结点
//    p=L; //刚开始先指向头结点，头结点是第0个结点（一般不存数据）
//    while(p!=NULL && j<i-1) //用一个while循环找到第i-1个结点
//    {
//        p=p->next;
//        j++;
//    }
//  	return InsertNextNode(p,e);
//}
//bool InsertPriorLNode(LNode *p,int e)
//{
//    if(p==NULL) return false;
//    LNode *s=(LNode *)malloc(sizeof(LNode));
//    if(s==NULL) return false;	//内存分配失败
//    s->next=p->next;
//    p->next=s;	//新结点s放到p之后
//    s->data=p->data;	//将p中元素复制到s中
//    p->data=e;		//将新元素e放到p中，类似于前插操作
//    return true;
//}
bool InsertPriorLNode(LNode *p,LNode *s)
{
    if(p==NULL || s==NULL) return false;
    s->next=p->next;
    p->next=s;
    int temp=p->data;	//设置一个临时变量存储p的数据
    p->data=s->data;
    s->data=temp;
    return true;
}
bool ListDelete(LinkList &L,int i,int &e)
{
    if(i<1) //位序肯定是大于等于1的
        return false;
    LNode *p; //指针p指向当前扫描到的结点
    int j=0; //j用来表示当前p指向的是第几个结点
    p=L; //刚开始先指向头结点，头结点是第0个结点（一般不存数据）
    while(p!=NULL && j<i-1) //用一个while循环找到第i-1个结点
    {
        p=p->next;
        j++;
    }
    if(p==NULL) 
        return false;
    if(p->next==NULL) //第i-1个结点之后已经没有结点
        return false;
    LNode *q=p->next;	//让q指向要被删除的结点
    p->next=q->next;	//将*q结点从链中断开
    e=q->data;			//用e返回元素的值
    free(q);		//释放结点的存储空间
    return true;//删除成功
}

//删除指定结点p
bool DeleteNode(LNode *p)
{
    if(p==NULL) return false;
    LNode *q=p->next;		//令q指向*p的后继结点
    p->data=p->next->data;	//和后继结点交换数据
    p->next=q->next;		//将*q从链中断开
    free(q);				//释放后继结点的存储空间
    return true;
}

//按位查找，返回第i个元素（带头结点）
LNode *GetElem(LinkList L,int i)
{
	if(i<0) return NULL;
    LNode *p;	//指针p指向当前扫描到的结点
    int j=0;	//j表示当前p指向的是哪个结点
    p=L;		//L指向头结点，头结点是第0个结点
    while(p!=NULL && j<i)	//循环找到第i个结点
    {
        p=p->next;
        j++;
	}
    return p;
}
bool ListInsert(LinkList &L,int i,int e)
{
    if(i<1) //位序肯定是大于等于1的
        return false;
    LNode *p=GetElem(L,i-1);
  	return InsertNextNode(p,e);
}
//按值查找，找到数据元素==e的结点
LNode *LocateElem(LinkList L,int e)
{
    LNode *p=L->next;
    //从第一个结点开始查找数据为e的结点
    while(p!=NULL && p->data!=e)
    {
        p=p->next;
    }
    return p;//找到后返回该结点指针，否则返回NULL
}
int Length(LinkList L)
{
    int len=0;//统计表长
    LNode *p=L;
    while(p->next!=NULL)
    {
        p=p->next;
        len++;
    }
    return len;
}
int main()
{
	LinkList L;
	InitList(L);
	ListInsert(L,1,1);
	ListInsert(L,2,2);
	ListInsert(L,3,3);
	ListInsert(L,4,4);
	LNode *a=GetElem(L,2);
	printf("%d\n",a->data);
	printf("%d\n",Length(L));
	return 0;
}

2.2双链表

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

2.2.1 初始化双链表

bool InitDLinkList(DLinkList &L)
{
	L=(DNode *)malloc(sizeof(DNode));
	if(L==NULL) return false;
	L->prior=NULL;		//头结点的prior永远指向NULL
	L->next=NULL;		//头结点之后暂时还没有结点
	return true;
}
//判断链表是否为空
bool Empty(DLinkList L)
{
    if(L->next==NULL) return true;
    else return false;
}

2.2.2 双链表的插入和删除

//在p结点之后插入s结点
bool InsertNextDNode(DNode *p,DNode *s)
{
	if(p==NULL || s==NULL)
		return false;
	s->next=p->next;
	if(p->next!=NULL)	//如果p结点之后还有结点
		p->next->prior=s;
	s->prior=p;
	p->next=s;
	return true;
}
//删除p结点的后继结点
bool DeleteNextDNode(DNode *p)
{
	if(p==NULL) return false;
	DNode *q=p->next;		//找到p的后继结点q
	if(q==NULL)	return false;	//若p没有后继，返回false
	p->next=q->next;		
	if(q->next!=NULL)		//q结点不是最后一个结点
		q->next->prior=p;
	free(q);				//释放结点空间
	return true;
}
void Destory(DLinkList &L)	//循环释放各个数据结点
{
    while(L->next!=NULL)
        DeleteNextDNode(L);
    free(L);		//释放头结点
    L=NULL;			//头结点指向NULL
}

2.2.3 双链表的遍历

//后向遍历
while(p->next!=NULL)
{
    //todo
    p=p->next;
}
//前向遍历
while(p->prior!=NULL)
{
    //todo
    p=p->prior;
}

2.3循环单链表

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

bool InitList(LinkList &L)
{
	L=(LNode *)malloc(sizeof(LNode));
	if(L==NULL)	return false;
	L->next=L;			//头结点的next指向头结点
	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;
}

2.4 循环双链表

typedef struct DNode{
    ElemType data;
    struct DNode *prior,*next;
}DNode,*DLinkList;
//初始化空的循环双链表
bool InitDlinkList(DLinkList &L)
{
    L=(DLnode *)malloc(sizeof(DNode));
    if(L==NULL)
        return false;
    L->prior=L;		//头结点的prior指向头结点
    L->next=L;		//头结点的next指向头结点
    return true;
}
//判断循环双链表是否为空
bool Empty(DLinkList L)
{
    if(L->next==L)
        return true;
    else true false;
}
//判断结点p是否为循环双链表的的表尾结点
bool isTail(DLinkList L,DNode *p){
    if(p->next==NULL) return true;
    else return false;
}
int main()
{
    DLinkList L;
    InitDLinkList(L);
    return 0;
}

//在p结点之后插入s结点
bool InsertNextNode(DNode *p,DNode *s)
{
    s->next=p->next;
    p->next->prior=s;
    s->prior=p;
    p->next=s;
}

2.5 静态链表

#include<stdio.h>
#define MaxSize 10	//静态链表的最大长度
typedef struct {	//静态链表结构类型的定义
	int data;		//存储数据元素
	int next;		//下一个元素的数组下标
}SLinkList[MaxSize];

struct Node{
	int data;		
	int next;
};

int main()
{
	struct Node x;
	printf("size-x:%d\n",sizeof(x));
	struct Node a[MaxSize];
	printf("size-a:%d\n",sizeof(a));
	SLinkList b;
	printf("size-b:%d\n",sizeof(b));
	return 0;
}

output:

size-x:8
size-a:80
size-b:80

3.顺序表和链表的比较

3.1 逻辑结构

都属于线性表，都是线性结构（数据元素之间只存在一对一的关系）

3.2 存储结构

顺序表：

  • 优点：支持随机存取，存储密度高
  • 缺点：大片连续空间分配不方便，改变容量不方便

链表

  • 优点：离散的小空间分配方便，改变容量方便
  • 缺点：不可随机存取，存储密度低

3.3 基本操作

3.3.1创建：

顺序表:需要预分配大片连续空间。若分配空间过小，则之后不方便拓展容量；若分配空间过大，则浪费内存资源。即便是动态分配，容量可以改变，但是需要移动大量元素，时间代价高。

链表：只需要分配一个头结点（也可以不用头结点，只声明一个头指针），之后方便拓展

3.3.2销毁：

顺序表：

​ 静态分配：静态数组 （系统自动回收）

​ 动态分配：动态数组 （malloc，free） 需要手动free释放；malloc和free必须成对出现

链表：依次删除各个结点（free）

3.3.4 插入/删除:

顺序表:插入/删除元素都要将后续元素都后移/前移；时间复杂度O（n），时间开销主要来自于移动元素

若数据元素很大，则移动的时间代价很高

链表：插入/删除元素只需修改指针即可；时间复杂度O（n），时间开销主要来自于查找元素

查找元素的时间代价更低

3.3.5 查找

顺序表：

​ 按位查找：O（1）

​ 按值查找：O（n），若表内元素有序，可在更短时间内找到

链表：

​ 按位查找：O（n）

​ 按值查找：O（n）

3.4 适用场景

顺序表 链表
弹性（可扩容） × √
增、删 × √
查 √ ×

3.5 答题思路：

逻辑结构......

存储结构......

基本操作......

补充说明：

引用调用：

#include<iostream>
using namespace std;

void test(int x)
{
	x=1024;
	cout<<"x:"<<x<<endl;
}
int main()
{
	int x=1;
	cout<<"x:"<<x<<endl;
	test(x);
	cout<<"x:"<<x<<endl;
	return 0;
}

//x:1
//x:1024
//x:1

#include<iostream>
using namespace std;

void test(int &x)
{
	x=1024;
	cout<<"x:"<<x<<endl;
}
int main()
{
	int x=1;
	cout<<"x:"<<x<<endl;
	test(x);
	cout<<"x:"<<x<<endl;
	return 0;
}

//x:1
//x:1024
//x:1024

标签：结点,return,LNode,int,next,data,线性表
From： https://www.cnblogs.com/Jinx8823/p/17467534.html

相关文章

  • 第2章-线性表习题
    P1708#include<stdio.h>#include<iostream>usingnamespacestd;voidreverse(inta[],intn,intm,intsize){ for(inti=0;i<size;i++){ a[i]=i+1; } for(inti=0;i<size;i++) cout<<a[i]<<""; cout<<endl;......
  • 每日记录(线性表链式存储结构（链表）)
    链表的基本概念建议每次写的时候都加一个头节点各结点由两个域组成：数据域：存储元素数值数据指针域：存储直接后继结点的存储位置结点：数据元素的存储映像。由数据域和指针域两部分组成链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构单链表......
  • 每日记录(2.4线性表的应用)
    有序表的合并已知线性表La和Lb中的数据元素按值非递减有序排列,现要求将La和Lb归并为一个新的线性表Lc,且Lc中的数据元素仍按值非递减有序排列。La=(1,7,8)Lb=(2,4,6,8,10,11)Lc=(1,2,4,6,7,8,8,10,11)0.新建一个链表新建一个空表C，直接在A和B中每次选取最小值......
  • 每日记录(数据结构 第二章 线性表() )
     线性表的定义：存在唯一一个“第一个”元素存在唯一一个“最后一个”元素除第一个元素外，每一个元素都有且只有一个前驱除最后一个元素外，每个元素都有且只有一个后继一、线性表顺序存储结构（顺序表）0.线性表的基本概念线性表强调元素在逻辑上紧密相邻，所以首先想到用数组存储。但是......
  • [学习笔记]数据结构_线性表_顺序表and单链表
    线性表线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面上的概念。线性表的基本操作boolInitList(&L)//初始化表，构造一个空的线性表intLength(L)//求表长。返回线性表L的长度，即L中数据元素的个数intLocateElem(L,e)//按......
  • 线性表的顺序存储结构
    线性表的顺序存储结构标签（空格分隔）：DS线性表顺序存储1.线性表的顺序存储结构#defineMAXSIZE20//数组最大长度typedefstruct{ElemeTypedata[MAXSIZE];//数组顺序存储元素，data即为存储空间的起始位置intlength;//线性表当前长度:表中元素的个数length<=MAXSIZE}SqLi......
  • 线性表的链式存储结构
    线性表的链式存储结构标签（空格分隔）：DS线性表链式存储1.线性表的单链表存储结构typedefstructNode{ElemTypedata;//数据域structNode*next;//指针域}Node,*pNode;//节点，节点指针typedefstructNode*LinkList;//头指针指向头节点2.单链表的读取第i个元......
  • 初级数据结构--线性表
    线性表定义线性表是具有相同数据类型n(n>=0)个数据元素的有限序列。当n=0时线性表为一个空表。顺序表实现方式：动态分配、静态分配特点：随机访问储存密度高扩展容量不方便插入删除数据元素不方便......
  • 线性表
    1、线性表：最常用最简单的数据结构，是一个n个数据元素的有限序列。2、理解重点：顺序存储，任意存取3、实现线性表前的一些宏定义以及typedef1#defineLIST_INIT_SIZE100//存储空间初始分配量2#defineLISTINCREMENT10//存储空间的分配增量34#defineERROR05#defin......
  • Problem E: STL——灵活的线性表
    HomeWebBoardProblemSetStandingStatusStatisticsProblemE:STL——灵活的线性表TimeLimit:1Sec  MemoryLimit:128MBSubmit:5192  Solved:2169[Submit][Status][WebBoard]Description数组和链表是我们熟知的两种线性结构，但是它们不够......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99