实验内容：
１．利用尾插法建立一个双向链表。
２．遍历双向链表。
３．实现双向链表中删除一个指定元素。
４．在非递减有序双向链表中实现插入元素e仍有序的算法。
５．判断双向链表中元素是否对称，若对称返回 1，否则返回 0。
６．设元素为正整型，实现算法把所有奇数排列在偶数之前。
７．在主函数中设计一个简单菜单，调用上述算法。
实验说明：
双向链表的类型定义
typedef int ElemType； // 元素类型
typedef struct DuLNode
{
ElemType data;
DuLNode *prior, *next;
} DuLNode, *pDuLinkList;
源代码
#include <iostream>
#include <time.h>
#include <stdlib.h>
#include <iomanip>
using namespace std;
typedef int ElemType;
typedef struct DuLNode
{
ElemType data;
struct DuLNode *prior, *next;
} DuLNode, *pDuLinkList;
pDuLinkList DuLinkLinst_Init() //建立双向链表
{
int n;
DuLNode *phead, *tmp, *p;
srand(unsigned(time(NULL)));
cout << "输入建立链表的元素个数：";
cin >> n;
phead = new DuLNode;
phead->next = phead;
phead->prior = phead;
p = phead;
for (int i = 0; i < n; i++)
{
tmp = new DuLNode;
tmp->data = rand() % 100;
tmp->prior = p;
p->next = tmp;
p = tmp;
}
p->next = phead;
phead->prior = p;
return phead;
}
void DuLinkList_Display(pDuLinkList phead) //输出双向链表
{
DuLNode *p;
p = phead->next;
while (p != phead)
{
cout << setw(4) << p->data;
p = p->next;
}
cout << endl;
}
void DuLinkList_Free(pDuLinkList phead) //释放双链表
{
DuLNode *p, *t;
p = phead->next;
while (p != phead)
{
t = p;
p = p->next;
delete t;
}
delete p;
}
void DuLinkList_Del(pDuLinkList phead, ElemType x) //删除指定元素
{
DuLNode *p1, *p2;
p1 = phead->next;
p2 = phead;
while (p1)
{
if (x == p1->data)
{
p2->next = p1->next;
p1->next->prior = p2;
delete p1;
return;
}
p2 = p1;
p1 = p1->next;
}
cout << "指定元素未找到！" << endl;
}
void DuLinkList_Sort(pDuLinkList phead) //排序
{
DuLNode *p;
int count = 0, i = 0;
ElemType *num, tmp;
p = phead->next;
if (p == phead)
{
cout << "双向链表为空！" << endl;
return;
}
while (p != phead)
{
count++;
p = p->next;
}
num = new ElemType[count];
p = phead->next;
while (p != phead)
{
num[i++] = p->data;
p = p->next;
}
for (int k = 0; k < count - 1; k++)
for (int j = 0; j < count - k - 1; j++)
if (num[j] > num[j + 1])
{
tmp = num[j];
num[j] = num[j + 1];
num[j + 1] = tmp;
}
p = phead->next;
i = 0;
while (p != phead)
{
p->data = num[i++];
p = p->next;
}
delete[] num;
}
void DuLinkList_Insert(pDuLinkList phead, ElemType elem) //插入一个元素
{
DuLNode *p, *tmp;
p = phead->next;
while (p != phead)
{
if (elem <= p->data)
break;
p = p->next;
}
tmp = new DuLNode;
tmp->data = elem;
tmp->next = p;
tmp->prior = p->prior;
p->prior->next = tmp;
p->prior = tmp;
}
int DuLinkList_symmetry(pDuLinkList phead) //链表中元素是否对称
{
DuLNode *p1, *p2;
p1 = phead->prior;
p2 = phead->next;
while (p1 != p2)
{
if (p1->data != p2->data)
{
return 0;
}
p1 = p1->prior;
p2 = p2->next;
}
return 1;
}
void DuLinkList_jiousort(pDuLinkList phead) //奇数在偶数前面
{
DuLNode *p1, *p2;
p1 = phead->next;
p2 = p1->next;
if (p1 == phead)
{
cout << "双向链表为空！" << endl;
return;
}
if (p2 == phead)
{
return;
}
while (p1 != phead)
{
if ((p1->data) % 2 != 0)
{
p2 = p1;
p1 = p1->next;
p1->prior = p2->prior;
p2->prior->next = p1;
p2->next = phead->next;
phead->next->prior = p2;
phead->next = p2;
p2->prior = phead;
}
else
p1 = p1->next;
}
}
int main()
{
DuLNode *L = NULL;
ElemType t;
int num;
cout << "1:利用尾插法建立一个双向链表" << endl;
cout << "2:遍历双向链表" << endl;
cout << "3:双向链表中删除一个指定元素" << endl;
cout << "4:在非递减有序双向链表中实现插入元素e仍有序的算法。" << endl;
cout << "5:判断双向链表中元素是否对称，若对称返回 1，否则返回 0" << endl;
cout << "6:设元素为正整型，实现算法把所有奇数排列在偶数之前" << endl;
cout << "7:退出" << endl;
while (true)
{
cout << "请输入一个数字选项:";
cin >> num;
switch (num)
{
case 1:
{
L = DuLinkLinst_Init();
cout << "L双向链表为：";
DuLinkList_Display(L);
cout << endl;
}break;
case 2:
{
cout << "双向链表为：";
DuLinkList_Display(L);
cout << endl;
}break;
case 3:
{
cout << "输入需要删除的元素：";
cin >> t;
DuLinkList_Del(L, t);
cout << "双向链表为：";
DuLinkList_Display(L);
cout << endl;
}break;
case 4:
{
cout << "输入要插入的元素：";
cin >> t;
DuLinkList_Sort(L);
DuLinkList_Insert(L, t);
cout << "双向链表为：";
DuLinkList_Display(L);
cout << endl;
}break;
case 5:
{
if(DuLinkList_symmetry(L)==1)
cout << "双向链表中元素对称" << endl;
else
cout << "双向链表中元素不对称" << endl;
cout << endl;
}break;
case 6:
{
DuLinkList_jiousort(L);
cout << "双向链表为：";
DuLinkList_Display(L);
cout << endl;
}break;
case 7:
{
DuLinkList_Free(L);
cout << endl;
return 0;
}break;
default:
cout << "输入错误！请重新输入！" << endl;
cout << endl;
}
}
return 0;
}
运行截图：
image
网友评论