C++ 单链表的基本操作
实验二：单链表的基本操作
编写一个完整的程序，实现单链表的建立、插入、删除、输出等基本操作。
（1）建立一个带头结点的单链表。
（2）计算单链表的长度，然后输出单链表。
（3）查找值为x的直接前驱结点q。
（4）删除值为x的结点。
（5）把单向链表中元素逆置（不允许申请新的结点空间）。
（6）已知单链表中元素递增有序，请写出一个高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，他们的值可以和表中的元素相同，也可以不同）。
（7）同（6）的条件，试写一高效的算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同），同时释放被删结点空间，并分析你的算法时间复杂度。
（8）利用（1）建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。
（9）在主函数中设计一个简单的菜单，分别测试上述算法。
代码
#include <stdio.h>
#include
<stdlib.h >
typedef struct node
{
int data;
struct node * next;
}Lnode, * LinkList;
int m = sizeof(Lnode);
/* 建立新的链表 */
void Bulid_List( LinkList root )
{
int num;
LinkList s, p;
s = root->next;
int n;
printf( "请输入新建链表的长度n数据:\n" );
scanf( "%d", &n );
printf( "请依次建立链表：" );
for ( int i = 0; i < n; i++ )
{
scanf( "%d", &num );
s->data = num;
p = (LinkList) malloc( m );
s->next = p;
s = p;
s->next = NULL;
}
printf( "链表已建立！\n" );
}
/* 对链表的输出，包括长度和元素 */
void OutPut_list( LinkList root )
{
int len = 0;
LinkList s;
s = root->next;
if ( s->next == NULL )
printf( "单链表无数据，请先新建单链表。\n" );
else
{
while ( s->next != NULL )
{
s = s->next;
len++;
}
printf( "单链表的长度为：%d\n", len );
printf( "单链表的数据如下:\n" );
s = root->next;
while ( s->next != NULL )
{
printf( "%d ", s->data );
s = s->next;
}
printf( "\n" );
}
}
void Find_list( LinkList root, int x )
{
LinkList s, p;
if ( root->next->next == NULL )
printf( "单链表无数据，请先新建单链表。\n" );
else
{
s = root->next;
p = root->next->next;
if ( s->data == x )
printf( "此X值无前驱结点。\n" );
else
{
while ( p->next != NULL )
{
if ( p->data == x )
{
printf( "此X值的前驱结点的值为：%d\n", s->data );
return;
}
else
{
s = p;
p = p->next;
}
}
printf( "此链表不存在值为X的结点。\n" );
}
}
return;
}
void Delete_list( LinkList root, int x )
{
LinkList s;
int
flag;
if ( root->next->next == NULL )
printf( "单链表无数据，请先新建单链表。\n" );
else
{
flag = 0;
while ( root->next != NULL )
{
if ( root->next->data == x )
{
if ( root->next->next != NULL )
{
s = root->next;
root->next = root->next->next;
free( s );
flag = 1;
return;
}
}
else
root = root->next;
}
if ( flag == 0 )
printf( "待删除的数据不存在。\n" );
}
return;
}
LinkList NEW()
{
LinkList new_node;
new_node = (LinkList) malloc( m );
new_node->next = NULL;
new_node->data = 0;
return(new_node);
}
/* 分解链表 */
void Divid( LinkList head )
{
LinkList head_odd, head_even, p_odd, p_even, p, s;
head_odd = NEW();
head_even = NEW();
p = head->next;
p_odd = head_odd;
p_even = head_even;
while ( p != NULL )
{
s = p;
p = p->next;
if ( s->data % 2 == 0 )
{
p_odd->next = s;
p_odd = p_odd->next;
p_odd->next = NULL;
}
else
{
p_even->next = s;
p_even = p_even->next;
p_even->next = NULL;
}
}
printf( "构建成功！\n" );
printf( "奇数链表为：" );
p = head_even->next;
while ( p->next != NULL )
{
printf( "%d ", p->data );
p = p->next;
}
printf( "\n偶数链表为：" );
p = head_odd;
while ( p->next != NULL )
{
printf( "%d ", p->next->data );
p = p->next;
}
printf( "\n" );
}/* 6 */
}
void DelteAndFree_list( LinkList root )
{
LinkList s, p, t, k;
int min, max;
if ( root == NULL )
printf( "单链表无数据，请先新建单链表。\n" );
else
{
printf( "请输入所要min的值，max的值(min < max):\n" );
scanf( "%d%d", &min, &max );
s = root->next;
p = root;
while ( s->data < min )
{
s = s->next;
p = p->next;
}
t = p;
while ( s->data < max )
{
s = s->next;
t = t->next;
}
s = p->next;
p->next = t->next->next;
t->next = NULL;
while ( s->next != NULL )
{
k = s;
s = s->next;
free( k );
}
free( s );
}
return;
}
void DeleteCommon_list( LinkList root )
{
LinkList s, p, t;
if ( root->next->next == NULL )
printf( "单链表无数据，请先新建单链表。\n" );
else
{
s = root->next;
p = root->next->next;
while ( p->next != NULL )
{
if ( s->data == p->data )
{
t = p;
p = p->next;
s->next = p;
free( t );
}
else
{
s = s->next;
p = p->next;
}
}
}
return;
}
void Reserve_list( LinkList root ) /* 链表的逆置 */
{
LinkList s, p, t;
s = root->next;
root->next = NULL;
while ( s->next != NULL )
{
p = s->next;
s->next = root->next;
root->next = s;
s = p;
}
LinkList head;
head = (LinkList) malloc( m );
head->next = NULL;
t = root;
while ( t->next != NULL )
{
t = t->next;
}
t->next = head;
return;
}
void print() /* 打印菜单 */
{
printf( "\n菜单如下：\n" );
printf( "1.建立单链表\n" );
printf( "2.计算单链表的长度并输出\n" );
printf( "3.查找值为x的直接前驱结点q\n" );
printf( "4.删除值为x的节点\n" );
printf( "5.逆置单链表\n" );
printf( "6.将单链表递增排序后删除表中所有值大于mink且小于maxk的元素\n" );
printf( "7.将单链表递增排序后删除表中所有值相同的多余元素\n" );
printf( "8.分解单链表，一个为奇数，另一个为偶数\n" );
printf( "0.EXIT\n\n" );
printf( "请输入你选菜单的数字：\n" );
}
int main( void ) /* 循环菜单 */
{
LinkList root;
int x;
root = (LinkList) malloc( m );
root->next = NULL;
root->next = (LinkList) malloc( m );
root->next->next = NULL;
bool flag;
int op;
print();
while ( scanf( "%d", &op ) != EOF ) /* show_arr(&arr); */
{
flag = true;
switch ( op )
{
case 0:
flag = false;
break;
case 1:
Bulid_List( root );
break;
case 2:
OutPut_list( root );
break;
case 3:
printf( "请输入所要查找的x:\n" );
scanf( "%d", &x );
Find_list( root, x );
break;
case 4:
printf( "请输入所要删除值x:\n" );
scanf( "%d", &x );
Delete_list( root, x );
break;
case 5:
Reserve_list( root );
break;
case 6:
DelteAndFree_list( root );
break;
case 7:
DeleteCommon_list( root );
break;
case 8:
Divid( root );
break;
default:
printf( "您真笨，输入的数字非法，程序已退出！！\n" );
break;
}
if ( !flag )
{
printf( "程序将退出！！谢谢使用！！\n" );
break;
}
else{
print();
}
}
return(0);
}