线性表相关操作思想

   线性表,顾名思义,线性排列形成一个表状的结构.有两种存储结构,一为顺序存储模式,二为链表模式,各有所长,互相补足.

一、顺序存储结构

(1)特征及定义:用一段地址连续的存储单元依次存储线性表的数据元素,结构规整,多用数组来表示.

#define MAXSIZE 20    //存储空间初始分配量

typedef int ElemType;
typedef struct
{

<span style="white-space:pre">	</span>ElemType data[MAXSIZE];//数据存储数据元素，最大值为MAXSIZE，这是在申请一块大小为20的地址连续的存储单元
<span style="white-space:pre">	</span>int length;//线性表当前的长度<=MAXSIZE
}SqList;

 a.获取表中第i个位置元素算法思路：第i个元素即为表中数组下标为i-1的元素；其次，i的值必须在数组下标范围内。

 b.顺序存储结构形式的线性表插入算法思路：如果插入位置不合理，抛出异常；如果线性表的长度>=数组长度，则抛出异常或者动态的增加容量；从最后一个元素开始向前遍历，到第i个位置，分别将它们都向后移动一个位置；将要插入元素填入位置i处；表长+1。

<span style="font-size:12px;">

int ListInsert(Sqlist *L,int i,ElemType e)
{
<span style="white-space:pre">	</span>int k;
<span style="white-space:pre">	</span>if(L->length==MAXSIZE)//顺序线性表已满
		return 0;
	if(i<1||i>L->length+1)//i不在范围内
		return 0;
	if(i<=L->length)//若插入的数据位置不在表尾时
	{
		for(k=L->length-1;k>=i-1;k--)//将插入位置之后的数据元素向后移动一位
			L->data[k+1]=L->data[k];
	}
	L->data[i-1]=e;//插入新元素
	L->length++;
	return 1;
}</span>

 c.删除算法的思路：如果删除位置不合理，抛出异常；取出删除元素；从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置；表长-1。

<span style="font-family:SimSun;font-size:10px;">

int ListDelete(SqList *	L,int i,ElemType *e)
{
	int k;
	if(L->length==0)
		return 0;
	if(i<1||i>L->length)
		return 0;
	*e=L->data[i-1];
	if(i<L->length)
	{
		for(k=i;k<L->length;k++)
			L->data[k-1]=L->data[k];
	}
	L->length--;
	return 1;
}</span>

（3）优点：快速存取表中任意位置的元素，插入和删除操作需要移动大量元素，存储空间易产生碎片。

二、链表存储结构

typedef struct Node
{
	ElemType data;
	struct Node *next;
}Node;
typedef struct Node *LinkList;

(2)获取链表中第i个数据的算法思路：声明一个指针p指向链表的第一个节点，遍历链表，p不断后移，计数递增，遇到链表末尾指针为空，则说明第i个节点不存在，否则，查找成功，返回节点p的数据。

int GetElem(LinkList L,int i,ElemType *e)
{
	int j;
	LinkList p;
	p=L->next;
	j=1;
	while(p&&j<i)
	{
		p=p->next;
		++j;
	}
	if(!p||j>i)
		return 0;
	*e=p->data;
	return 1;
}</span>

   算法思路：首先查找第i个数据的位置，如（2）所述，查找成功后，建立一个空节点s，将需要插入的新元素赋值给s->data，然后进行插入思想中标准动作，指针转移：s->next=p->next,p->next=s这个地址转移顺序不能错，为什么呢，反过来转移，p->next已经被s给覆盖了，那s->next找谁去评理

int ListInsert(ListList *L,int i,ElemType e)
{
	int j;
	ListList p,s;
	p=*L;
	j=1;
	while(p&&j<i)
	{
		p=p->next;
		++j;
	}
	if(!p||j>i)
		return 0;
	s=(ListList)malloc(sizeof(Node));
	s->data=e;
	s->next=p->next;
	p->next=s;
	return 1;
}

(4)删除思想：欲删除第i个节点，意思就是让第i-1个节点的指针p绕过第i个直接指向第i+1个节点，即p->next=p->next->next;

   删除算法：重复获取过程，查找成功后按照删除思想操作，稍作改动另设指针q=p->next;p->next=q->next,将q指针所占的空间释放掉，利用free。

int ListDelete(ListList *L,int i,ElemType *e)
{
	int j;
	ListList p,q;
	p=*L;
	j=1;
	while(p&&j<i)
	{
		p=p->next;
		++j;
	}
	if(!p||j>i)
		return 0;
	q=p->next;
	p->next=q->next;
	*e=q->data;
	free(q);
	return 1;
}

   创建算法：声明一个指针p和计数器变量i；初始化空链表L;让L的头结点的指针指向NULL;循环生成新节点插入过程。相比而言，尾插法更好理解，头插法声明了一个指针的指针**

//头插法

void CreatListHead(ListList *L,int n)
{
	ListList p;
	int i;
	srand(time(0));
	*L=(ListList)malloc(sizeof(Node));
	(*L)->next=NULL;
	for(i=0;i<n;i++)
	{
		p=(ListList)malloc(sizeof(Node));
		p->data=rand()%100+1;
		p->next=(*L)->next;
		(*L)->next=p;
	}
}

//尾插法

void CreatListHead(ListList *L,int n)
{
<span style="white-space:pre">	</span>ListList p,r;
<span style="white-space:pre">	</span>int i;
<span style="white-space:pre">	</span>srand(time(0));
<span style="white-space:pre">	</span>*L=(ListList)malloc(sizeof(Node));
<span style="white-space:pre">	</span>r=*L;
<span style="white-space:pre">	</span>for(i=0;i<n;i++)
<span style="white-space:pre">	</span>{
<span style="white-space:pre">	</span>p=(ListList)malloc(sizeof(Node));
	p->data=rand()%100+1;
<span style="white-space:pre">	</span>r->next=p;
	r=p;
<span style="white-space:pre">	</span>}
<span style="white-space:pre">	</span>r->next=NULL;
}

int ClearList(ListList *L)
{
	ListList p,q;
	p=(*L)->next;
	while(p)
	{
		q=p->next;
		free(p);
		p=q;
	}
	(*L)->next=NULL;
	return 1;
}

最后

以上就是潇洒火龙果为你收集整理的线性表相关操作思想的全部内容，希望文章能够帮你解决线性表相关操作思想所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。