建立一个单链表，实现插入与删除功能

Question

要求：
1.建立一个按关键字有序的线性表，从键盘上输入一个数，将该数插入到表中，使该线性表插入数据后仍按关键字有序
2.建立一个线性表，从键盘上输入一个数，查找表中是否存在该数，若有则删除所有与该数相等的数

Answer 1

　　建立一个单链表，实现插入与删除功能的代码如下：
　　///单链表
　　#include<iostream>
　　using namespace std;
　　
　　typedef int elemtype; //数据类型模版
　　
　　struct Lnode //结点
　　{
　　elemtype data;
　　Lnode *next;
　　};
　　
　　///建表
　　void creat_Link(Lnode &head)
　　{
　　Lnode *p,*q;
　　int n;
　　p=new Lnode;
　　head=p;
　　cout<<"输入链表长度:"<<endl;
　　cin>>n;
　　cout<<"输入数据:"<<endl;
　　cin>>p->data;
　　q=p;
　　for(int i=1;i<=n-1;i++)
　　{
　　p=new Lnode;
　　//cout<<"输入数据:";
　　cin>>p->data;
　　q->next=p;
　　q=p;
　　}
　　q->next=NULL;
　　}
　　
　　///表的输出
　　void output_Link(Lnode *&head)
　　{
　　if(head==NULL)
　　{cout<<"空链表!"<<endl;
　　return;}
　　Lnode *q;
　　q=head;
　　//cout<<"此链表为:";
　　while(q!=NULL)
　　{
　　cout<<q->data<<" ";
　　q=q->next;
　　}
　　cout<<endl;
　　}
　　
　　
　　///表的插入
　　void insert_Link(Lnode *&head)
　　{
　　int i;
　　cout<<"输入要插入的位置:";
　　
　　cin>>i;
　　Lnode *q,*iq;
　　q=head;
　　for(int j=1;j<i;j++)
　　{
　　iq=q;
　　q=q->next;
　　}
　　
　　cout<<"输入插入的数据:";
　　Lnode *p;
　　p=new Lnode;
　　cin>>p->data;
　　p->next=iq->next;
　　iq->next=p;
　　cout<<endl;
　　
　　}
　　
　　///表的数据删除
　　void Delete_Link(Lnode *&head)
　　{
　　cout<<"输入删除的位置:";
　　int i;
　　cin>>i;
　　if(i==1)
　　head=head->next;
　　else
　　{
　　Lnode *p,*q;
　　q=head;
　　for(int j=1;j<i;j++)
　　{ p=q;
　　q=q->next;
　　}
　　p->next=q->next;
　　delete q;
　　cout<<endl;
　　}
　　}
　　
　　
　　int main()
　　{
　　Lnode *head;
　　head=NULL;
　　creat_Link(head);
　　
　　insert_Link(head);
　　output_Link(head);
　　Delete_Link(head);
　　output_Link(head);
　　return 0;
　　}
　　[扩展]
　　以“结点的序列”表示线性表称作线性链表（单链表），链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

Answer 2

#include<stdio.h>
#include<malloc.h>
#define LEN sizeof(struct Node)
typedef struct Node
{
int data;
struct Node *next;
}node;
int n;
node *Creat(void)
{
int data;
node *head;
node * p1=(node*)malloc(LEN);
node * p2=(node*)malloc(LEN);
head=NULL;
n=0;
puts("Please input a num:");
scanf("%d",&p1->data);
while(p1->data!=0)
{
n++;
if(n==1)
head=p1;
else
p2->next=p1;
p2=p1;
p1=(node*)malloc(LEN);
scanf("%d",&p1->data);
}
free(p1);
p1=NULL;
p2->next=NULL;
return head;
}
void Print(node *head)
{
node *p;
p=head;
if(head==NULL)
{
printf("No Records?!");
return;
}
else
do
{
printf("%d-->",p->data);
p=p->next;
}while(p!=NULL);
printf("\n");
}
node* Insert(node *head)
{
int data;
node *p0=(node*)malloc(LEN),*p1,*p2;
p1=head;
if(head==NULL)
{
printf("No Records?!");
return NULL;
}
puts("Please input a num to insert:");
scanf("%d",&p0->data);
while(p1->data<p0->data&&p1->next!=NULL)
{
p2=p1;
p1=p1->next;
}
if(p1->data>=p0->data)
{
if(p1==head)
head=p0;
else
p2->next=p0;
p0->next=p1;
}
else
printf("Not find!\n");
return head;
}
node *Delete(node *head)
{
node *p0,*p1,*p2,*p3;
p0=(node*)malloc(LEN);
if(head==NULL)
{
printf("No Reacord?!");
return NULL;
}
puts("Please input a num to delete:");
scanf("%d",&p0->data);
while(head->data==p0->data)
head=head->next;
p1=head;
if(head->next!=NULL)
do
{
p2=p1;
p1=p1->next;
while(p1!=NULL&&p1->data==p0->data)
{
p3=p1;
p1=p1->next;
free(p3);
}
p2->next=p1;
}while(p1!=NULL);
return head;
}
int main()
{
node *head;
head=Creat();
Print(head);
head=Insert(head);
Print(head);
head=Delete(head);
Print(head);
return 0;
}
Please input a num:
2 3 4 5 6 0
2-->3-->4-->5-->6-->
Please input a num to insert:
4
2-->3-->4-->4-->5-->6-->
Please input a num to delete:
5
2-->3-->4-->4-->6-->
Press any key to continue
VC6.0