首页 > 其他分享 >数据结构严蔚敏版精简版-线性表以及c语言代码实现

数据结构严蔚敏版精简版-线性表以及c语言代码实现

时间：2024-06-09 16:03:17浏览次数：20  
标签：Node last 线性表 next printf 精简版 first 严蔚敏版 size

线性表、栈、队列、串和数组都属于线性结构。线性结构的基本特点是除第一个元素无直接前驱，最后一个元素无直接后继之外，其他每个数据元素都有一个前驱和后继。

1 线性表的定义和特点

如此类由n（n大于等于0）个数据特性相同的元素构成的有限序列称为线性表。 线性表中元素的个数n定义为线性表的长度，n=0时称为空表。

对千非空的线性表或线性结构，其特点是：

(1)存在唯一的一个被称作“第一个＂的数据元素；

(2)存在唯一的一个被称作“最后一个＂的数据元素；

(3)除第一个之外，结构中的每个数据元素均只有一个前驱；

(4)除最后一个之外，结构中的每个数据元素均只有一个后继。

2 线性表的顺序存储表示

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，这种表示 也称作线性表的顺序存储结构或顺序映像。通常，称这种存储结构的线性表为顺序表(Sequential List)。其特点是，逻辑上相邻的数据元素，其物理次序也是相邻的。

2.1顺序表的操作

代码实现：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<malloc.h>
#define LONG 8//最大容量 
#define inc 3

typedef  int Elemtype;
typedef struct Seqlist{
	Elemtype *base;//基地址 
	int capacity;//最大容量 
	int size;//所含元素的多少 
}Seqlist; 
 
 
 bool INC(Seqlist *L)
 {
 	Elemtype *newbase=(Elemtype*)realloc(L->base,sizeof(Elemtype)*(L->capacity+inc));
 	if(newbase==NULL)
 	{
 		printf("满了，不能开辟空间");
 		return false;
	 }
	 L->base=newbase;
	 L->capacity+=inc;
	 return true;
 }
void InitSeqlist(Seqlist *L)//初始化 
{
	L->base=(Elemtype*)malloc(sizeof(Elemtype)*LONG);
	assert(L->base !=NULL);
	L->size=0;
	L->capacity=LONG;
	
}
void Push_back(Seqlist *L,Elemtype x)//尾插 
{
	
	if(L->size>=L->capacity&&!INC(L))
	{
		printf("满了");
		return;
	}
	L->base[L->size]=x;
	L->size++;
}
void show_list(Seqlist *L)//展示 
{
	for(int i ;i< L->size;i++)
	{
		printf("%d  ",L->base[i]);
	}
	printf("\n");
}
void Push_front(Seqlist *L,Elemtype x)//头插 
{
	if(L->size>=L->capacity&&!INC(L))
	{
		printf("满了，不能头插");
		return;
	}
	for(int i=L->size;i>0;i--)
	{
		L->base[i]=L->base[i-1];
	}
	L->base[0]=x;
	L->size++;
}
void pop_back(Seqlist *L)//尾部删除 
{
	if(L->size==0)
	{
		printf("空表不能尾部删除"); 
	}
	L->size--;
 } 
 void pop_front(Seqlist *L)//头部删除 
 {
 	if(L->size==0)
	{
		printf("空表不能头部删除"); 
	}
	for(int i=1;i<L->size;i++) 
	{
		L->base[i-1]=L->base[i];
	}
	L->size--;
 }
void insert_pos(Seqlist *L,int pos,Elemtype itim)
{
	if(L->size>=L->capacity)
	{
		printf("满了，不能按位置插");
		return;
	}
	if(pos<0 || pos>L->size )
	{
		printf("位置不和合法"); 
	}
	for(int i=L->size;i>pos;i--) 
	{
		L->base[i]=L->base[i-1];
	}
	L->base[pos]=itim;
	L->size++;
}
int find(Seqlist *L,Elemtype x)
{
	if(L->size==0)
	{
		printf("空表");
		return -1;
	}
	for(int i=0;i<L->size;i++)
	{
		if(L->base[i]==x)
		return i;
	 }
	 return -1;	 
}
int length(Seqlist *L)
{
	printf("长度为%d,容量为%d",L->size,L->capacity);
	return L->size;
}
void delete_pos(Seqlist *L,int pos)
{
	if(pos<0||pos>L->size)
	{
		printf("位置非法");
		return;
	}
	for(int i=pos;i<L->size;i++)
	{
		L->base[i]=L->base[i+1];
	}
	L->size--;
}
void delete_val(Seqlist *L,int x)
{
	int pos=find(L,x);
	if(pos==-1)
	{
		printf("数据不存在");
		return;
	}
	delete_pos(L,pos);
}

void sort(Seqlist *L)
{
	for(int i=0;i<L->size-1;i++)
	{
		for(int j=0;j<L->size-i-1;j++)
		{
			if(L->base[j]>L->base[j+1])
			{
				Elemtype tmp=L->base[j];
				L->base[j]=L->base[j+1];
				L->base[j+1]=tmp; 
			}
		}
	}
}

void resver(Seqlist *L)
{
	int head=0;
	int rear=L->size-1;
	while(1)
	{
		int tmp=L->base[head];
		L->base[head]=L->base[rear];
		L->base[rear]=tmp;
		head++;
		rear--;
		if(head>rear)
			break;
	}
	
	
	
}

void clear(Seqlist *L)
{
	L->size=0;
}

void destory(Seqlist *L)
{
	free(L->base);
	L->size=NULL;
	L->capacity=0;
	L->size=0;
 }
  


int main1()
{	
	Seqlist L;
	InitSeqlist(&L);
		int setlect=1
	while(select)
	{
		printf("************************************\n");
		printf("* [1]push_back    [2]push_front    *\n");
		printf("* [3]show_list    [4]pop_back      *\n");
		printf("* [5]pop_front    [6]insert_pos    *\n");
		printf("* [7]find         [8]length        *\n");
		printf("* [9]delete_pos   [10]delete_va    *\n");
		printf("* [11]sort        [12]resver       *\n");
		printf("* [13]clear [14]destroy     [0]quit_system   *\n");
		printf("************************************\n");
		printf("请选择"); 
		scanf("%d",&select); 
		if(select==0)
			break;
		
		switch(select)
		{
		case 1:
			printf("输入插的数据-1结束");
			while(scanf("%d",&itim),itim !=-1)
			{
			Push_back(&L,itim);
			}
			break;
		case 2:
			printf("请输入数据头插");
			scanf("%d",&itim);
			Push_front(&L,itim);
			break;
		case 3:
			show_list(&L); 
			break;
		case 4:
			pop_back(&L);
			break;
		case 5:
			pop_front(&L);
			break;
		case 6:
			printf("请输入插入数据");
			scanf("%d",&itim) ;
			printf("请输入位置");
			scanf("%d",&pos);
			insert_pos(&L,pos,itim);
			break;
		case 7:
			printf("输入查找数据");
			scanf("%d",&itim);
			pos=find(&L,itim);
			if(pos>=0)	
				printf("查找成功%d的位置在%d\n",itim,pos);
			else			
				printf("查找%d失败，没有找到\n",itim) ;
			
			break;
		case 8:
			printf("表的长度为%d\n",length(&L));
			break;
		case 9:
			printf("请输入要删除的位置：");
			scanf("%d",&pos);
			delete_pos(&L,pos);
			break; 
		case 10:
			printf("请输入要删除的数据：");
			scanf("%d",&itim);
			delete_val(&L,itim);
			break;
		case 11:
			sort(&L);
			break;
		case 12:
			resver(&L);
			break;
		case 13:
			clear(&L);
			break;
		case 14:
			destory(&L);
			break;
			
		}	
		
	}
	destory(&L);
}

2.2顺序表的优缺点

顺序表可以随机存取表中任一元素，其存储位置可用一个简单、直观的公式来表示。然而， 从另一方面来看，这个特点也造成了这种存储结构的缺点：在做插入或删除操作时，需移动大量元素。另外由千数组有长度相对固定的静态特性，当表中数据元素个数较多且变化较大时， 操作过程相对复杂，必然导致存储空间的浪费。所有这些问题，都可以通过线性表的另一种表 示方法�式存储结构来解决。

3 线性表的链式表示

用单链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的。换句话说，指 针为数据元素之间的逻辑关系的映像，则逻辑上相邻的两个数据元素其存储的物理位置不要求紧 邻，由此，这种存储结构为非顺序映像或链式映像。

链表增加头结点的作用：

(1)便于首元结点的处理增加了头结点后，首元结点的地址保存在头结点（即其“前驱”结点）的指针域中，则对链表 的第一个数据元素的操作与其他数据元素相同，无需进行特殊处理。

(2)便于空表和非空表的统一处理 当链表不设头结点时，假设L为单链表的头指针，它应该指向首元结点，则当单链表为长度 n为0的空表时，L指针为空。

3.1单链表的操作

包含链表的头插头删，尾差尾删，逆置，排序等操作。

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<assert.h>
#define Elemtype int
typedef struct Node
{
	Elemtype data;
	struct Node *next;
}Node,*PNode;

typedef struct List
{
	PNode first;//头指针 
	PNode last;//尾指针 
	size_t size;
}List;
void Initlist(List *L)//初始化 
{
	L->first=L->last=(Node*)malloc(sizeof(Node));
	L->first->next=NULL; 
	L->last->next=NULL; 
	L->size=0; 
}
void push_back(List *L,Elemtype x)//尾插 
{
	Node *s=(Node*)malloc(sizeof(Node));
	assert(s!=NULL);
	s->data=x;
	s->next=NULL;
	L->last->next=s;
	L->last=s;
	L->size++;
}
void push_front(List *L,Elemtype x)//头插 
{
	Node *s=(Node*)malloc(sizeof(Node));
	assert(s!=NULL);
	s->data=x;
	s->next=L->first->next;
	L->first->next=s;
	if(L->size==0)
	{
		L->last=s;
		
	}
	L->size++;
}
void show_list(List *L)//打印链表 
{
	if(L->size==0)
	{
		printf("为空表");
		return; 
	}
	Node *p=L->first->next;
	while(p!=NULL)
	{
		printf("%d-->",p->data);
		p=p->next;
	}
	printf("NULL\n");
}

void pop_back(List *L)//尾删 
{
	if(L->size==0)
	{
		printf("空表");
		return;
	}
	Node *p=L->first;
	while(p->next !=L->last)
		p=p->next;
	free(p->next);
	L->last=p;
	L->size--;
	p->next=NULL;//或L->last->next=NULL; 
	
}
void pop_front(List *L)//头删 
{
	if(L->size==0)
	{
		printf("空表");
		return;
	}
	Node *p=L->first->next;
	L->first->next=p->next;
	free(p);
	L->size--; 
	if(L->size==1)
	{
		L->last=L->first;
	}
 } 
void insert_val(List *L,Elemtype x)//在排序的链表中插入数据，并使其不变 
{	
	Node *s=(Node*)malloc(sizeof(Node));
	s->data=x;
	s->next=NULL;
	Node *p=L->first;
	while(p->next!=NULL && p->next->data<x)
	{
		p=p->next;
	}
	/*
	printf("%d",p->data);*/
	if(p->next==NULL)
	{
		printf("到头了");
		printf("%d",p->next) ;
		L->last=s;

	}
	
	s->next=p->next;
	p->next=s;
	L->size++;
}
Node* find(List *L,Elemtype key)//查找节点 
{
	Node *p=L->first->next;
	while(p!=NULL&&p->data!=key)
	{
	p=p->next;
	}
	return p;
}
int length(List *L)
{
	return L->size;
}

void delete_val(List *L,Elemtype x)//删除指定元素 
{
Node *p=find(L,x);
	if(L->size==0)
		return;
	
	
	else if(p==NULL)
    {
		printf("不存在");
		return;
		}
	else if(p==L->last)
	{	
		pop_back(L);
	}
	else
	{
	
	Node *q=p->next;
	p->data=q->data;
	p->next=q->next;
	free(q);
	L->size--;
	}
	
}
void sort(List *L)//链表排序 
{
	if(L->size==0||L->size==1)
	{
		return ;
	}
	Node *s=L->first->next;
	Node *q=s->next;
	L->last=s;
	L->last->next=NULL;
	while(q!=NULL)//q为第二段 
	{
	int data;
	data=q->data;
	printf("%d",data); 
	insert_val(L,data);
	q=q->next;
	}
}
void resver(List *L)//链表逆置 
{
	if(L->size==1||L->size==0)
		return;
	Node *s=L->first;
	Node *q=s->next;
	L->last=s;
	L->last->next=NULL;
	while(q!=NULL)//q为第二段 
	{
	int data;
	data=q->data;
	//printf("%d",data); 
	push_front(L,data);
	q=q->next;
	}
}
void clear(List *L)//清空 
{
	if(L->size==0)
	return;
	Node *p=L->first->next;
	Node *s=p->next;
	while(p!=NULL)
	{
		L->first->next=p->next;
		free(p);
		p=L->first->next;
		
	}
	L->last=L->first;
	L->size=0;
}

void destory(List *L)//销毁 
{
	clear(L);
	free(L->first);
	L->first=L->last=NULL;
	
}
int  main()
{
	List L;
	Elemtype itim;
	int pos;
	Initlist(&L);
	int select=1;
	while(select)
	{
		printf("************************************\n");
		printf("* [1]push_back    [2]push_front    *\n");
		printf("* [3]show_list    [4]pop_back      *\n");
		printf("* [5]pop_front    [6]insert_val    *\n");
		printf("* [7]find         [8]length        *\n");
		printf("* [9]delete_val   [10]sort         *\n");
		printf("* [11]resver      [12]clear        *\n");
		printf("* [13]destroy     [0]quit_system   *\n");
		printf("************************************\n");
		printf("请选择");
		scanf("%d",&select);
		if(select==0)
			break;
		switch(select)
		{
			case 1:
				printf("请输入要出入的数据(-1结束)");
				while(scanf("%d",&itim),itim!=-1)
				{
				push_back(&L,itim);
				}
				break;
			case 2:
				printf("请输入数据头插（-1结束）");
				while(scanf("%d",&itim),itim!=-1)
				{
				push_front(&L,itim);
				}
				break;
			case 3:
				show_list(&L);
				break;
			case 4:
				pop_back(&L);
				break;
			case 5:
				pop_front(&L);
				break;
			case 6:
				printf("请输入数据:");
				scanf("%d",&itim);
				insert_val(&L,itim);
				break;
			case 7:
				printf("请输入要查找的数据：");
				scanf("%d",&itim);
				
				
				if(find(&L,itim)==NULL)
				{
					printf("不存在"); 
				 } 
				 else
				 {
				 	printf("存在");
				 }
				 break;
			case 8:
				printf("大小为%d",length(&L));
				break;
			case 9:
				printf("请输入要删除的数据:");
				scanf("%d",&itim);
				delete_val(&L,itim);
				break;
			case 10:
				sort(&L); 
				break;
			case 11:
				resver(&L);
				break; 
			case 12:
				clear(&L);
				break;
			//case 13:
			//	
			//	break;
			default:
				printf("数据不合法");
				break; 
		}
	} destory(&L);
}

3.2单循环链表的操作与实现

包含单循环链表的头插头删，尾差尾删，逆置，排序等操作。

#define  Elemtype int
#include<stdio.h>
#include<malloc.h>
typedef struct Node
{
	Elemtype data;
	struct Node *next; 
}Node,*PNode;

typedef struct List
{
	PNode first;
	PNode last;
	int size;
 } List;
 
 void initlist(List *L)//初始化 
 {
 	Node *s=(Node*)malloc(sizeof(Node));
 	L->first=L->last=s;
 	L->last->next=L->first;
	L->size=0;
 }
 
 Node *_buynode(Elemtype x)//创建节点 
 {
 	Node *s=(Node*)malloc(sizeof(Node));
 	s->data=x;
 	s->next=NULL;
 	return s;
 }
 void show_list(List *L)//打印链表 
 {
 	Node *p=L->first->next;
 	while(p!=L->first)
 	{
 		printf("%d-->",p->data);
 		p=p->next;
	 }
	 
 }
 
 void push_back(List *L,Elemtype x)//尾插 
 {
 	Node *s=_buynode(x);
 	L->last->next=s;
 	L->last=s;
 	L->last->next=L->first;
 	L->size++; 
 }
 void push_front(List *L,Elemtype x)//头插 
 {
 	Node *s=_buynode(x);
 	s->next=L->first->next;
 	L->first->next=s;
 	
 	if(L->size==0)
 	{
 		L->last=s;
	 }
	L->size++;
 }
 void pop_front(List *L)//头删 
 {
 	if(L->size==0)
 	return;
 	
 	Node *s=L->first->next;
 	Node *p=s->next;
 	L->first->next=p;
 	free(s);
 	if(L->size==1)
 	{
 		L->last=L->first;
	 }
 	L->size--;
 }
 void pop_back(List *L)//尾删 
 {
 	if(L->size==0)
 	{
 		return;
	 }
	 Node *p=L->first;
	 while(p->next!=L->last)
	 {
	 p=p->next;
	 }
	 free(p->next);
	 p->next=L->first;
	 L->last=p;
	 L->size--;
  } 
void insert_val(List *L,Elemtype x)//插入表，使其保持顺序不变 
{

	Node *p=L->first;
	while(p->next!=L->last&&p->next->data<x)
	{
		p=p->next;
	}
	if(p->next->next==L->first&&p->next->data<x)//p->next==L->last; 因为L->last->next=L->first; 
	{
		push_back(L,x);
	}
	else
	{	Node *s=_buynode(x);
		s->next=p->next;
		p->next=s;
		L->size++;
	}
}
Node* find(List *L,Elemtype x)//查找 
{
	if(L->size==0)
	return NULL;
	Node *p=L->first->next;
	while(p!=L->first&&p->data!=x)
	{
		p=p->next;
	}
	if(p==L->first)
	{
		return NULL;
	}
	return p;
 } 
 
 int length(List *L)
 {
 	return L->size;
  } 
  void delete_val(List *L,Elemtype x)//指定值删除 
  {
  	if(L->size==0)
  	return;
  	Node *p=find(L,x);
  	if(p==NULL)
  	{
	printf("不存在");
	return;
	} 
	if(p==L->last)
	{
		pop_back(L);
	}
	else{
		Node *s=p->next;
		p->data=s->data;
		p->next=s->next;
		free(s);
		L->size--;
	}
  }
  
void sort(List *L)//排序 
{	if(L->size==0||L->size==1)
	return;
	Node *p=L->first->next;
	Node *s=p->next;//第二段 
	L->last->next=NULL;
	L->last=p;
	L->last->next=L->first;
	
	while(s!=NULL)
	{	Node *z=s->next;;
		int x=s->data;
	//	printf("%d",x); 
		insert_val(L,x);
		L->size--;
		free(s); 
		s=z;
	}
	
}
void resver(List *L)//逆置 
{
	if(L->size==0||L->size==1)
	return;
	Node *p=L->first->next;
	Node *s=p->next;//第二段 
	L->last->next=NULL;
	L->last=p;
	L->last->next=L->first;
	
	while(s!=NULL)
	{	Node *z=s->next;;
		int x=s->data;
	//	printf("%d",x); 
		push_front(L,x);
		free(s);
		L->size--;
		s=z;
	}
}
void clear(List *L)//清空 
{
	Node *p=L->first->next;
	while(p!=L->first)
	{
		L->first->next=p->next;
		free(p);
		p=L->first->next;
	}
	L->size=0;
	L->last=L->first;
	L->last->next=L->first;
}
void destory(List *L)//销毁 
{
	clear(L);
	free(L->first);
	free(L->last);
	L->first=L->last=NULL;
}
int  main()
{
	List L;
	Elemtype itim;
	int pos;
	initlist(&L);
	int select=1;
	while(select)
	{
		printf("************************************\n");
		printf("* [1]push_back    [2]push_front    *\n");
		printf("* [3]show_list    [4]pop_back      *\n");
		printf("* [5]pop_front    [6]insert_val    *\n");
		printf("* [7]find         [8]length        *\n");
		printf("* [9]delete_val   [10]sort         *\n");
		printf("* [11]resver      [12]clear        *\n");
		printf("* [13]destroy     [0]quit_system   *\n");
		printf("************************************\n");
		printf("请选择");
		scanf("%d",&select);
		if(select==0)
			break;
		switch(select)
		{
			case 1:
				printf("请输入要出入的数据(-1结束)");
				while(scanf("%d",&itim),itim!=-1)
				{
				push_back(&L,itim);
				}
				break;
			case 2:
				printf("请输入数据头插（-1结束）");
				while(scanf("%d",&itim),itim!=-1)
				{
				push_front(&L,itim);
				}
				break;
			case 3:
				show_list(&L);
				break;
				
			case 4:
				pop_back(&L);
				break;
			case 5:
				pop_front(&L);
				break;
				
			case 6:
				printf("请输入数据:");
				scanf("%d",&itim);
				insert_val(&L,itim);
				break;
			case 7:
				printf("请输入要查找的数据：");
				scanf("%d",&itim);
				
				
				if(find(&L,itim)==NULL)
				{
					printf("不存在"); 
				 } 
				 else
				 {
				 	printf("存在");
				 }
				 break;
			case 8:
				printf("大小为%d",length(&L));
				break;
			case 9:
				printf("请输入要删除的数据:");
				scanf("%d",&itim);
				delete_val(&L,itim);
				break;
			case 10:
				sort(&L); 
				break;
			case 11:
				resver(&L);
				break; 
			case 12:
				clear(&L);
				break;
			//case 13:
			//	
			//	break;*/
			default:
				printf("数据不合法");
				break; 
		}
	} destory(&L);
}

3.3双循环链表的实现

包含双循环链表的头插头删，尾差尾删，逆置，排序等操作。

#include<stdio.h>
#include<malloc.h>
#include<assert.h>
#define Elemtype int
typedef struct Node{
	Elemtype data;
	struct Node *next;
	struct Node *prio;
}Node;

typedef struct List{
	Node *first;//前驱 
	Node *last;//后继 
	int size;
}List;


Node*  _buynode(Elemtype x)//创建节点 
{
	Node *p=(Node*)malloc(sizeof(Node));
	p->data=x;
	p->next=p->prio=NULL;
	return p;
}
void InitList(List *L)//初始化 
{
	Node *s=(Node*)malloc(sizeof(Node));
	L->first=s;
	L->first->next=NULL;
	L->last=s;
	L->first->prio=L->last;
	L->last->next=L->first;
}
void show_list(List *L)//打印链表 
{	if(L->size==0)
	{
		printf("空表");
		return;
	}
	Node *p=L->first->next;
	while(p!=L->first)
	{
	printf("%d-->",p->data);
	p=p->next;
	}
}

void push_back(List *L,Elemtype x)//尾插 
{
	Node *p=_buynode(x);
	p->next=L->last->next;
	p->next->prio=p;
	p->prio=L->last;
	L->last->next=p;
	L->last=p;
	L->size++;
} 
void push_front(List *L,Elemtype x)//头插 
{
	Node *p=_buynode(x);
	p->next=L->first->next;
	p->next->prio=p;
	L->first->next=p;
	p->prio=L->first; 
	
	if(L->size==0)
	{
		L->last=p;
		p->next=L->first;
		L->first->prio=L->last;
	}
	L->size++;
}

void pop_back(List *L)//尾删 
{
	if(L->size==0)
	{
		return;
	}
	Node *p=L->last;
	L->last=p->prio;
	p->next->prio=p->prio;
	p->prio->next=p->next;
	free(p);
	L->size--;
}
void pop_front(List *L)//头删 
{
	if(L->size==0)
	return;
	Node *p=L->first->next;
	p->next->prio=p->prio;
	p->prio->next=p->next;
	free(p);
	if(L->size==1)
	{
		L->last=L->first;
		
	}
	L->size--;
}

void insert_val(List *L,Elemtype x )//有序的链表，插入x后保持有序 
{
	Node *p=L->first;
	while(p->next!=L->first&&p->next->data<x)
		p=p->next;
	if(p->next==L->first)
	{
	push_back(L,x);
	} 
	else{
		Node *s=_buynode(x);
		s->next=p->next;
		s->next->prio=s;
		s->prio=p;
		p->next=s;
		L->size++;
	}


}

Node* find(List *L,Elemtype x)//查找 
{
	Node *p=L->first->next;
	while(p->next!=L->first&&p->data!=x)
	{
		p=p->next;
	}
	if(p->next==L->first&&p->data!=x)
		return NULL;
	return p;
}

int length(List *L)
{
	return L->size;
}

void delete_val(List *L,Elemtype x)//删除指定值 
{
	Node *p=find(L,x);
	if(p==NULL)
	{
		return;
	}
	else{
		p->prio->next=p->next;
		p->next->prio=p->prio;
		free(p);
	}
	L->size--;
 } 
 void sort(List *L)//排序 
 {
 	if(L->size==0||L->size==1)
 	{return;
	 }
	Node *s=L->first->next;
	Node *q=s->next;
	L->last->next=NULL;
	L->last=s;
	L->last->next=L->first;
	L->first->prio=L->last;
	while(q!=NULL)
	{
		s=q;
		q=q->next;
		Node *p=L->first->next;

	while(p->next!=L->last&&p->next->data<s->data)
		p=p->next;
	if(p->next==L->last&&p->next->data<s->data)
	{
	s->next=L->last->next;
	s->next->prio=s;
	s->prio=L->last;
	L->last->next=s;
	L->last=s;
	} 
	else{
		
		s->next=p->next;
		s->next->prio=s;
		s->prio=p;
		p->next=s;
	}
	}
	
 }
 void resver(List *L)//逆置 
 {
 	if(L->size==0||L->size==1)
 	{return;
	 }
	Node *s=L->first->next;
	Node *q=s->next;
	L->last->next=NULL;
	L->last=s;
	L->last->next=L->first;
	L->first->prio=L->last;
	while(q!=NULL)
	{
		s=q;
		q=q->next;
		s->next=L->first->next;
		s->next->prio=s;
		L->first->next=s;
		s->prio=L->first;
	}
 }
void clear(List *L)//清空 
{	if(L->size==0)
	return;
	Node *p=L->first->next;
	while(p!=L->first)
	{
	p->next->prio=L->first;
	L->first->next=p->next;
	free(p);
	p=L->first->next;
	L->size--;
}
L->last=L->first ;
}
void destory(List *L)
{
	clear(L);
	free(L->first);
	L->first=L->last=NULL;
}
int  main()
{
	List L;
	Elemtype itim;
	int pos;
	InitList(&L);
	int select=1;
	while(select)
	{
		printf("************************************\n");
		printf("* [1]push_back    [2]push_front    *\n");
		printf("* [3]show_list    [4]pop_back      *\n");
		printf("* [5]pop_front    [6]insert_val    *\n");
		printf("* [7]find         [8]length        *\n");
		printf("* [9]delete_val   [10]sort         *\n");
		printf("* [11]resver      [12]clear        *\n");
		printf("* [13]destroy     [0]quit_system   *\n");
		printf("************************************\n");
		printf("请选择");
		scanf("%d",&select);
		if(select==0)
			break;
		switch(select)
		{
			case 1:
				printf("请输入要出入的数据(-1结束)");
				while(scanf("%d",&itim),itim!=-1)
				{
				push_back(&L,itim);
				}
				break;
			case 2:
				printf("请输入数据头插（-1结束）");
				while(scanf("%d",&itim),itim!=-1)
				{
				push_front(&L,itim);
				}
				break;
			case 3:
				show_list(&L);
				break;
				
			case 4:
				pop_back(&L);
				break;
			case 5:
				pop_front(&L);
				break;
				
			case 6:
				printf("请输入数据:");
				scanf("%d",&itim);
				insert_val(&L,itim);
				break;
			case 7:
				printf("请输入要查找的数据：");
				scanf("%d",&itim);
				
				
				if(find(&L,itim)==NULL)
				{
					printf("不存在"); 
				 } 
				 else
				 {
				 	printf("存在");
				 }
				 break;
			case 8:
				printf("大小为%d",length(&L));
				break;
			case 9:
				printf("请输入要删除的数据:");
				scanf("%d",&itim);
				delete_val(&L,itim);
				break;
			case 10:
				sort(&L); 
				break;
			case 11:
				resver(&L);
				break; 
			case 12:
				clear(&L);
				break;
			
			/*case 13:
				destory(&L);
				break;*/
			default:
				printf("数据不合法");
				break; 
		}
	} //destory(&L);
}

4 顺序表和链表的比较

4.1空问性能的比较

(1)存储空间的分配 顺序表的存储空间必须预先分配，元素个数扩充受一定限制，易造成存储空间浪费或空间溢出现象；而链表不需要为其预先分配空间，只要内存空间允许，链表中的元素个数就没有限制。 基于此，当线性表的长度变化较大，难以预估存储规模时，宜采用链表作为存储结构。

(2)存储密度的大小 链表的每个结点除了设置数据域用来存储数据元素外，还要额外设置指针域，用来存储指示 元素之间逻辑关系的指针，从存储密度上来讲，这是不经济的。所谓存储密度是指数据元素本身 所占用的存储量和整个结点结构所占用的存储量之比，

存储密度越大，存储空间的利用率就越高。显然，顺序表的存储密度为1，而链表的存储密度小于1。

4.2 时间性能的比较

(l)存取元素的效率 顺序表是由数组实现的，它是一种随机存取结构，指定任意一个位置序号都可以在0(1) 时间内直接存取该位置上的元素，即取值操作的效率高；而链表是一种顺序存取结构，按位置访问链表中元素时，只能从表头开始依次向后遍历链表，直到找到第i个位置上的元素，时间复杂度为O(n), 即取值操作的效率低。

(2)插入和删除操作的效率对比

链表在确定插入或删除的位置后，插入或删除操作无需移动数据，只需要修改指针， 时间复杂度为0(1)。顺序表进行插入或删除时，平均要移动表中近一半的结点，时间复杂度为O(n)。

标签：Node,last,线性表,next,printf,精简版,first,严蔚敏版,size
From： https://blog.csdn.net/qq_37040743/article/details/139497557

相关文章

  • 数据结构（C语言严蔚敏版）——第二章 线性表
    前言：    对这一章节的学习，我深有体会，只有把链表这一重点弄清楚，才算开始真正的正式学习数据结构，刚开始学习链表的朋友可能会感到有点绕脑，但是当你掌握链表以后，你会发现其实原来学习编程还是很有意思的，慢慢在学习中找到成就感，不断收获。   当然，这章的重点还是在......
  • 一款WPF的精简版MVVM框架——stylet框架(MVVM绑定、依赖注入等)
    今天偶然知道一款叫做stylet的MVVM框架，挺小巧的，特别是它的命令触发方式，简单粗暴，让人感觉很巴适，现在我做一个简单的demo来顺便来分享给大家。本地创建一个WPF项目，此处我使用.NET8来创建。然后引用stylet最新的nuget包。 然后删掉App.xaml里面自带的启动项删掉以后： sty......
  • 一款WPF的精简版MVVM框架——stylet框架的初体验(包括MVVM绑定、依赖注入等操作)
    今天偶然知道一款叫做stylet的MVVM框架，挺小巧的，特别是它的命令触发方式，简单粗暴，让人感觉很巴适，现在我做一个简单的demo来顺便来分享给大家。本地创建一个WPF项目，此处我使用.NET8来创建。然后引用stylet最新的nuget包。 然后删掉App.xaml里面自带的启动项删掉以后： styl......
  • 数据结构·线性表
    线性表一、逻辑结构和基本操作1.逻辑结构具有相同数据类型的n个数据元素的有限序列，表长n，n=0为空表表头：第一个元素表尾：最后一个元素除第一个元素外，每个元素有且仅有一个直接前驱除最后一个元素外，每个元素有且仅有一个直接后继2.基本操作initList(&L);len(L);locateE......
  • 【第二节】C/C++数据结构之线性表
    目录一、线性表基本说明1.1基本概念1.2抽象数据类型1.3存储结构1.4插入与删除的区别1.5顺序存储和链式存储的优缺点二、链表2.1基本概念2.2抽象数据类型2.3单链表的定义2.4单链表的基本操作2.5单链表模板形式的类定义与实现三、单向循环链表四、双链表......
  • 【数据结构实验】迷宫问题——线性表
    目录实验目的实验内容（题目） 实验环境 程序代码实验分析 实验目的掌握并理解线性表的存储结构定义，包括线性表的顺序存储结构与链式存储结构。学习并掌握线性表的基本操作实现，如插入、删除、查找、遍历等基本运算。明确线性表的存储结构特点，包括它们的时间和空间复杂......
  • 数据结构—线性表
    线性表的定义：    线性表是具有相同特性的数据元素的一个有限序列，类似于数组。    线性表中的元素都有一个直接前驱和直接后继，除了第一个首元素和最后一个元素线性表的实现：    使用线性表模拟动态数组的实现：                //.......
  • 设线性表中每个元素有两个数据项k1和k2,现对线性表按一下规则进行排序：先看数据项k1，k1
    题目：设线性表中每个元素有两个数据项k1和k2,现对线性表按一下规则进行排序：先看数据项k1，k1值小的元素在前，大的在后；在k1值相同的情况下，再看k2，k2值小的在前，大的在后。满足这种要求的排序方法是（）A.先按k1进行直接插入排序，再按k2进行简单选择排序B.先按k2进行直接插入排序，再按k1进行......
  • 【考研数据结构知识点详解及整理——C语言描述】第二章线性表的定义和基本操作
    25计算机考研，数据结构知识点整理（内容借鉴了王道408＋数据结构教材），还会不断完善所整理的内容，后续的内容也会不断更新（可以关注），若有错误和不足欢迎各位朋友指出!目录 一.线性表的定义二.线性表的基本操作一.线性表的定义（1）线性表是具有相同数据类型的n(n>0)个数据元素的有......
  • 第二章 线性表（4）
    2.7.2链表逆置问题（反转链表问题）该部分参考了408之2023年算法题预测和力扣相关题解解决这类问题，有三种方法，递归法、迭代法和头插法。头插法是教科书中创建链表的头插法在反转链表中的应用，但是需要依赖反转的第一个结点的前驱结点，如果该结点没有前驱结点，需要先创建一个du......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99