数据结构线性表设计与实现 4（1）

阅读量：772 次

发布时间：2019-03-24

本文共 11417 字，大约阅读时间需要 38 分钟。

目录：

线性表基本概念

1）线性表定义 2）数学定义

3）性质 4）练习

线性表的顺序存储结构

1）基本概念 2）设计与实现 3）优点和缺点

线性表的链式存储

1）基本概念 2）设计与实现 3）优点和缺点

1.线性表基本概念

1）线性表定义

线性表(List)是零个或多个数据元素的集合

线性表中的数据元素之间都是有顺序的

线性表中的数据元素个数是有限的

线性表中的数据元素类型必须相同

2）数学定义

线性表是具有相同类型的n（大于等于0）个数据元素的有限序列（a1,a2,a3,....,an）其中，ai是表项，n是表长度

3）性质

a0为线性表的第一个元素，只有一个后继

an为线性表的最后一个元素，只有一个前驱

除a0和an外的其它元素ai，既有前驱，又有后继

线性表能够逐项访问和顺序存取

4）练习

下面的关系中可以用线性表描述的是：

A.班级中同学的友谊关系（N:N）

B.公司中的上下级关系（1:N）

C.冬天图书馆排队占座关系（1：？）

D.花名册上名字之间的关系（1:1）

5）线性表的操作

创建线性表；销毁线性表；清空线性表；将元素插入线性表；将元素从线性表中删除；获取线性表中某个位置的元素；获取线性表的长度

线性表在程序中表现为一种特殊的数据类型

线性表的操作在程序中的表现为一组函数

ADT抽象层：

#ifndef _WBH_LIST_H_#define _WBM_LIST_H_typedef void List;typedef void ListNode;//创建并返回一个空的线性表List* List_Create();//销毁一个线性表listvoid List_Destroy(List* list);//将一个线性表list中的所有元素清空，线性表回到创建时的初始状态void List_Clear(List* list);//返回一个线性表list中的所有元素个数int List_Length(List* list);//向一个线性表list的pos位置处插入新元素nodeint List_insert(List* list,ListNode* node,int pos);//获取一个线性表list的pos位置处的元素ListNode* List_Get(List* list,int pos);//删除一个线性表的list的pos位置处的元素，返回值为被删除的元素，NULL表示删除失败ListNode* List_Delete(List* list,int pos);#endif//注意int List_insert(List* list,ListNode* node,int pos);(重点：分离思想)

2.线性表的顺序存储结构

1）基本概念

顺序存储定义：线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素

2）设计与实现

a.插入元素算法：

判断线性表是否合法——>判断插入位置是否合法——>把最后一个元素到插入位置的元素后移一个位置

——>将新元素插入——>线性表长度加1

b.获取元素操作

判断线性表是否合法——>判断位置是否合法——>直接通过数组下标的方式获取元素

c.删除元素算法

判断线性表是否合法——>判断删除位置是否合法——>将元素取出——>将删除位置后的元素分别向前移动一个位置

——>线性表的长度减1

线性表顺序存储设计与实现测试框架：

#include 
   
    #include 
    
     #include 
     
      #include "seqlist.h"SeqList* SeqList_Create(int capacity){	return NULL;}void SeqList_Destroy(SeqList* list){	return;}void SeqList_Clear(SeqList* list){	return ;}int SeqList_Length(SeqList* list){	return 0;}int SeqList_Capacity(SeqList* list){	return 0;}int SeqList_Insert(SeqList* list, SeqListNode* node, int pos){	return 0;}SeqListNode* SeqList_Get(SeqList* list, int pos){	return NULL;}SeqListNode* SeqList_Delete(SeqList* list, int pos){	return NULL;}

#ifndef  __MY_SEQLIST_H__ #define __MY_SEQLIST_H__typedef void SeqList;typedef void SeqListNode;SeqList* SeqList_Create(int capacity);void SeqList_Destroy(SeqList* list);void SeqList_Clear(SeqList* list);int SeqList_Length(SeqList* list);int SeqList_Capacity(SeqList* list);int SeqList_Insert(SeqList* list, SeqListNode* node, int pos);SeqListNode* SeqList_Get(SeqList* list, int pos);SeqListNode* SeqList_Delete(SeqList* list, int pos);#endif  //__MY_SEQLIST_H__

#include 
   
    #include 
    
     #include 
     
      #include "seqlist.h"typedef struct _Teacher{	int age;	char name[64];}Teacher;typedef struct _Teacher2{	int age;	char name[64];}Teacher2;typedef struct _Teacher3{	int age;	char name[64];	int age3;}Teacher3;void main(){	int		ret = 0, i = 0;	SeqList* list = NULL;	Teacher t1, t2, t3, t4,t5;	t1.age = 31;	t2.age = 32;	t3.age = 33;	t4.age = 34;	t5.age = 35;	list = SeqList_Create(10);	if (list == NULL)	{		printf("func SeqList_Create() ret :%d \n", ret);		return ;	}	ret = SeqList_Insert(list, (SeqListNode*) &t1, 0); //头插法	ret = SeqList_Insert(list, (SeqListNode*) &t2, 0); //头插法	ret = SeqList_Insert(list, (SeqListNode*) &t3, 0); //头插法	ret = SeqList_Insert(list, (SeqListNode*) &t4, 0); //头插法	ret = SeqList_Insert(list, (SeqListNode*) &t5, 0); //头插法	//遍历	for (i=0; i
      
       age:%d ", tmp->age);	}	//删除链表中的节点	while( SeqList_Length(list) > 0 )	{		SeqList_Delete(list, 0);	}	system("pause");	/*	typedef void SeqList;	typedef void SeqListNode;	SeqList* SeqList_Create(int capacity);	void SeqList_Destroy(SeqList* list);	void SeqList_Clear(SeqList* list);	int SeqList_Length(SeqList* list);	int SeqList_Capacity(SeqList* list);	int SeqList_Insert(SeqList* list, SeqListNode* node, int pos);	SeqListNode* SeqList_Get(SeqList* list, int pos);	SeqListNode* SeqList_Delete(SeqList* list, int pos);	*/	return ;}

//实现底层库#include 
   
    #include 
    
     #include 
     
      #include "seqlist.h"//在结构体中套2级指针//typedef struct _tag_SeqList{	int length;	int capacity;	unsigned int **node;   //int* node[]}TSeqList;SeqList* SeqList_Create(int capacity){	int ret = 0;	TSeqList *tmp = NULL;	tmp = (TSeqList *)malloc(sizeof(TSeqList));	if (tmp == NULL)	{		ret = -1;		printf("func SeqList_Create() err:%d \n", ret);		return NULL;	}	memset(tmp, 0, sizeof(TSeqList));   //void *memset(void *s, int ch, size_t n);函数解释：将s中当前位置后面的n个字节 （typedef unsigned int size_t ）用 ch 替换并返回 s 。	//根据capacity 的大小分配节点的空间	tmp->node = (unsigned int **)malloc(sizeof(unsigned int *) * capacity);	if (tmp->node  == NULL)	{		ret = -2;		printf("func SeqList_Create() err: malloc err %d \n", ret);		return NULL;	}	tmp->capacity = capacity;	tmp->length = 0;	return tmp;}void SeqList_Destroy(SeqList* list){	TSeqList *tlist = NULL;	if (list == NULL)	{		return ;	}	tlist = (TSeqList *)list;	if (tlist->node != NULL)	{		free(tlist->node);	}		free(tlist);	return ;}//清空链表 //回到初始化状态void SeqList_Clear(SeqList* list){	TSeqList *tlist = NULL;	if (list == NULL)	{		return ;	}	tlist = (TSeqList *)list;	tlist->length = 0; 	return ;}int SeqList_Length(SeqList* list){	TSeqList *tlist = NULL;	if (list == NULL)	{		return -1;	}	tlist = (TSeqList *)list;	return tlist->length;}int SeqList_Capacity(SeqList* list){	TSeqList *tlist = NULL;	if (list == NULL)	{		return -1;	}	tlist = (TSeqList *)list;	return tlist->capacity;}int SeqList_Insert(SeqList* list, SeqListNode* node, int pos){	int i =0, ret = 0;	TSeqList *tlist = NULL;	if (list == NULL || node==NULL ||  pos<0)	{		ret = -1;		printf("fun SeqList_Insert() err:%d \n", ret);		return ret;	}	tlist = (TSeqList*)list;	//判断是不是满了	if (tlist->length >= tlist->capacity)	{		ret = -2;		printf("fun SeqList_Insert() (tlist->length >= tlist->capacity) err:%d \n", ret);		return ret;	}	//容错修正  6个长度 容量20;用户pos10位置插入..	if (pos>=tlist->length)	{		pos = tlist->length; //	}	//1 元素后移	for(i=tlist->length; i>pos; i--)	{		tlist->node[i] = tlist->node[i-1];		//a[7] = a[6]	}	// i = 3	// 2插入元素	tlist->node[i] = node;      //会不会丢数据，需要在64环境机器上做测试	tlist->length ++;	return 0;}SeqListNode* SeqList_Get(SeqList* list, int pos){	int i =0;	SeqListNode *ret = 0;	TSeqList *tlist = NULL;	if (list == NULL ||  pos<0)	{		printf("fun SeqList_Get() err:%d \n", ret);		return NULL;	}	tlist = (TSeqList*)list;	ret = (void *)tlist->node[pos];	return ret;}SeqListNode* SeqList_Delete(SeqList* list, int pos){	int i = 0;	SeqListNode *ret = 0;	TSeqList *tlist = NULL;	if (list == NULL ||  pos<0) //检查	{		printf("fun SeqList_Delete() err:%d \n", ret);		return NULL;	}	tlist = (TSeqList*)list;	ret = (SeqListNode *)tlist->node[pos]; //缓存pos的位置	 	for (i=pos+1; i
      
       length; i++)  //pos位置后面的元素前移	{		tlist->node[i-1] = tlist->node[i];	}	tlist->length --;	return ret;}

4)优点和缺点

优点：无需为线性表中的逻辑关系增加额外的空间；可以快速的获取表中合法位置的元素

缺点：插入和删除操作需要移动大量元素；当线性表长度变化较大时难以确定存储空间的容量

2.线性表的链式存储

1）基本概念

为了表示每个数据元素与其直接后继元素之间的逻辑关系，每个元素除了存储本身的信息外，还需要存储指示其直接后继的信息

表头结点：链表中的第一个节点，包含指向第一个数据元素的指针以及链表自身的一些信息

数据节点：链表中代表数据元素的结点，包含指向下一个数据元素的指针和数据元素的信息

尾结点：链表中的最后一个数据节点，其下一个元素指针为空，表示无后继

2）设计与实现

在C语言中可以用结构体来定义链表中的指针域，链表中的表头节点也可以用结构体实现

备注：

循环遍历时，遍历第1次，指向位置0

循环遍历时，遍历第2次，指向位置1

循环遍历时，遍历第3次，指向位置2

循环遍历时，遍历第n次，指向位置n-1

如果想返回位置n的元素的值，需要怎么做：ret=current->next;

此问题是：指向头结点的指针移动n次和第n个元素之间的关系？

3）优点和缺点

优点：

无需一次性定制链表的容量；插入和删除操作无需移动数据元素

缺点：

数据元素必须保存后继元素的位置信息；获取指定数据的元素操作需要顺序访问之前的元素

链表技术领域推演：

链表内部数据结构分析：

链表线性存储算法分析——插入：

链表线性存储算法分析——删除：

实现代码：

typedef void LinkList;/*typedef struct_tag_LinkListNode LinkListNode;struct _tag_LinkListNode{LinkListNode * next;};*/typedef struct _tag_LinkListNode{	struct _tag_LinkListNode * next;}LinkListNode;LinkList* LinkList_Create();void LinkList_Destroy(LinkList* list);void LinkList_Clear(LinkList* list);int LinkList_Length(LinkList* list);int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);LinkListNode* LinkList_Get(LinkList* list, int pos);LinkListNode* LinkList_Delete(LinkList* list, int pos);#endif

#include 
   
    #include 
    
     #include 
     
      #include"linklist.h"typedef struct _tag_LinkList{	LinkListNode header;	int length;}TLinkList;LinkList* LinkList_Create(){	TLinkList *ret = NULL;	ret = (TLinkList *)malloc(sizeof(TLinkList));	meset(ret, 0, sizeof(TLinkList));	ret->length = 0;         //    	ret->header.next = NULL;     //		return ret;}void LinkList_Destroy(LinkList* list){	if (list != NULL)	{		free(list);		list = NULL;	}	return;}//让链表恢复到初始化状态void LinkList_Clear(LinkList* list){	TLinkList *tList = NULL;	if (list == NULL)	{		return;	}	tList = (TLinkList *)list;	tList->length = 0;	tList->header.next = NULL;	return;}int LinkList_Length(LinkList* list){	TLinkList *tList = NULL;	if (list == NULL)	{		return;	}	tList = (TLinkList *)list;	return tList->length;}int LinkList_Insert(LinkList* list, LinkListNode* node, int pos){	int ret = 0,i=0;	LinkListNode *current = NULL;	TLinkList *tList = NULL;	if (list == NULL || node == NULL || pos < 0)	{		ret = 0;		printf("func LinkList_Insert() err:%d\n", ret);		return ret;	}	tList = (TLinkList *)list;	current = &(tList->header);	for(i=0;i
      
       next!=NULL);i++)	{		current = current->next;	}	//1   让node连接后续链表	node->next = current -> next;	//2  让前面的链表连接新的node节点	current->next = node;	tList->length++;	return 0;}LinkListNode* LinkList_Get(LinkList* list, int pos){	int ret = 0, i = 0;	LinkListNode *current = NULL;	TLinkList *tList = NULL;	if (list == NULL || pos < 0)	{		ret = 0;		printf("func LinkList_Insert() err:%d\n", ret);		return NULL;	}	tList = (TLinkList *)list;	current = &(tList->header);          //让辅助指针变量指向链表的头部	for (i = 0; i
       
        next != NULL); i++)         //跳pos次	{		current = current->next;	}		return current->next;}LinkListNode* LinkList_Delete(LinkList* list, int pos){		int i = 0;	LinkListNode *current = NULL;	LinkListNode *ret = NULL;	TLinkList *tList = NULL;	if (list == NULL || pos < 0)	{		printf("func LinkList_Insert() err:%d\n", ret);		return NULL;	}	tList = (TLinkList *)list;	current = &(tList->header);          //让辅助指针变量指向链表的头部	for (i = 0; i
        
         next != NULL); i++) //跳pos次 { current = current->next; } //缓存被删除的节点位置 ret = current->next; //连线 current->next = ret->next; tList->length--; return ret;}

#include 
   
    #include 
    
     #include 
     
      #include "linklist.h"typedef struct Teacher{	LinkListNode node;        //第一个域（第一个元素）	int age;	char name{ 64 };}Teacher;void main(){	int len = 0,ret=0;	LinkList* list = NULL;	Teacher t1, t2, t3, t4, t5;	t1.age = 31;	t2.age = 32;	t3.age = 33;	t4.age = 34;	t5.age = 35;	list=LinkList_Create();	if (list == NULL)	{		return;	}	len = LinkList_Length(list);	//链表的算法和具体业务节点的分离	ret= LinkList_Insert( list, (LinkListNode*)(&t1), int 0);	ret = LinkList_Insert(list, (LinkListNode*)(&t2), int 0);	ret = LinkList_Insert(list, (LinkListNode*)(&t3), int 0);	ret = LinkList_Insert(list, (LinkListNode*)(&t4), int 0);	ret = LinkList_Insert(list, (LinkListNode*)(&t5), int 0);	//遍历	for (i = 0; i < LinkList_Length(list); i++)	{		Teacher *tmp = (Teacher *)LinkList_Get(list, i);		if (tmp == NULL)		{			return;		}		printf("tmp->age:%d", tmp->age);	}	//删除链表	while (LinkList_Length(list)>0)	{		Teacher *tmp = (Teacher *)LinkList_Delete(list, 0);		if (tmp == NULL)		{			return;		}		printf("tmp->age:%d", tmp->age);	}	LinkList_Destroy(list);	system("pause");/*LinkList* LinkList_Create();void LinkList_Destroy(LinkList* list);void LinkList_Clear(LinkList* list);int LinkList_Length(LinkList* list);int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);LinkListNode* LinkList_Get(LinkList* list, int pos);LinkListNode* LinkList_Delete(LinkList* list, int pos);*/return;}

转载地址：http://pzqkk.baihongyu.com/

你可能感兴趣的文章