实验4-线性表实验.md

实验4-线性表实验

第一题 带头结点的循环双链表的建立、输出、判断是否对称和链接，源代码如下：

#include <iostream>
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
using namespace std;

typedef int ElemType;

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


//建立，使用尾插法创建一个初始含n个结点的循环双链表
DLinkList CreateListFromTail(int n)
{
	DLinkList  h, s, p;
	int i;
	h = (DNode*)malloc(sizeof(DNode));
	h->next = h->prior = NULL;
	p = h;
	for (i = 1; i <= n; i++)
	{
		s = (DNode*)malloc(sizeof(DNode));
		cout << "请输入循环双链表的第" << i << "个元素的值：";
		cin >> s->data;
		p->next = s;
		s->prior = p;
		p = s;
	}
	p->next = h;
	h->prior = p;
	return h;
}

//输出双链表
void ListTra(DLinkList h)
{
	DLinkList p;
	p = h->next;
	while (p != h)
	{
		cout << p->data << ',';
		p = p->next;
	}
	cout << endl;
}

//判断链表是否对称，如果对称返回1，否则返回0
int IsSamenode(DLinkList h)
{
	DLinkList p, q;
	p = h->next;
	q = h->prior;
	while (p != q && p->prior != q)
	{
		if (q->data != p->data)
			return 0;
		p = p->next;
		q = q->prior;
	}
	return 1;
}

//链接
void LinkList(DLinkList s1,DLinkList s2)
{
	DLinkList p, q;
	p = s1->prior;
	q = s2->next;
	p->next = q;
	q->prior = p;
	q = s2->prior;
	q->next = s1;
	s1->prior = q;
}

第二题 逆转链表

//将单向链表逆转
void revsList(LinkList h)
{
	LinkList p, r;
	p = h->next;
	h->next = h;
	while (p != h)
	{
		r = p->next;
		p->next = h->next;
		h->next = p;
		p = r;
	}
	ListTras(h);
}
//将单向循环链表逆转
void revsList(LinkList h)
{
	LinkList p, r;
	p = h->next;
	h->next = h;
	while (p != h)
	{
		r = p->next;
		p->next = h->next;
		h->next = p;
		p = r;
	}
	ListTras(h);
}

第三题 已知线性表中个数据元素值为整型且递增有序，设计算法删除线性表中所有大于min且小于max的结点，源代码如下：

链表

//第三题,
void a(LinkList h,int min,int max)
{
	LinkList p, q;
	q = h;
	p = h->next;
	while (p != NULL)
	{
		
		if (p->data < min) 
		{
			q = p;
		}
		else if(p->data > max)
		{
			q->next = p;
			return;
		}
		else
		{
			free(p);
		}
		p = p->next;
	}
}

顺序表

void a(SeqList *l, int min, int max)
{
	int i;
	int a = 0;
	int b = l->length - 1;
	for(i = 0;i<l->length;i++)
	{
		if (l->elem[i] < min) {
			a = i;
		}
		if (l->elem[i] > max) {
			b = i;
			break;
		}
	}
	int c = b - a - 1;
	for (i = b; i < l->length; i++) {
		l->elem[i - c] = l->elem[i];
	}
	l->length = l->length - c;
}