C++語言線性表的插入和刪除

ID:71259 · 發(fā)表于 2014-12-30 01:28

本帖最后由 daming 于 2014-12-30 02:14 編輯

#include<iostream.h>
struct node
{
int data;
node *next;
};
//建立一條升序鏈表 (尾插法:最后建立的結(jié)點(diǎn)是表頭，故應(yīng)降序輸入)
node *creat_sort()
{
node *p1,*head=NULL;
int a;
cout<<"建立一條有序鏈表，請輸入數(shù)據(jù)，以-1結(jié)束:\n";
cin>>a;
while(a!=-1){
p1=new node;
p1->data=a;
p1->next=head;
head=p1;
cin>>a;
}
return head;
}
//輸出鏈表上各個結(jié)點(diǎn)的值
void print(const node *head)
{
const node *p;
p=head;
cout<<"鏈表上各個結(jié)點(diǎn)的數(shù)據(jù)為：\n";
while(p!=NULL){
cout<<p->data<<'\t';
p=p->next;
}
cout<<endl;
}
//刪除鏈表上具有指定值的一個結(jié)點(diǎn)
node *delete_one_node(node *head,int num)
{
node *p1,*p2;
if(head==NULL){
cout<<"鏈表為空，無結(jié)點(diǎn)可刪!\n";
return NULL;
}
if(head->data==num){
p1=head;
head=head->next;
delete p1;
cout<<"刪除了一個結(jié)點(diǎn)!\n";
}
else{
p2=p1=head;
while(p2->data!=num&&p2->next!=NULL){
p1=p2;
p2=p2->next;
}
if(p2->data==num){
p1->next=p2->next;
delete p2;
cout<<"刪除了一個結(jié)點(diǎn)!\n";
}
else
cout<<num<<"鏈表上沒有找到要刪除的結(jié)點(diǎn)!\n";
}
return head;
}
//釋放鏈表的結(jié)點(diǎn)空間
void deletechain(node *h)
{
node *p1;
while(h){
p1=h;
h=h->next;
delete p1;
}
cout<<"已釋放鏈表的結(jié)點(diǎn)空間!\n";
}
//求鏈表的結(jié)點(diǎn)數(shù)
int count(node *head)
{
int n;
node *p;
p=head;
n=0;
while(p!=NULL){
n=n+1;
p=p->next;
}
return n;
}
////查找第k個結(jié)點(diǎn)
node *find(node *head,int k)
{
int i;
node *p;
i=1;
p=head;
while(i<k){
i++;
p=p->next;
}
return p;
}
//刪除鏈表上第K個結(jié)點(diǎn)
node *delete_k_node(node *head,int k)
{
int j=1;
node *p,*p1;
if(head==NULL){
cout<<"鏈表為空，無結(jié)點(diǎn)可刪!\n";
return NULL;
}
p=head;
if(k==1){
p=head;
head=head->next;
delete p;
cout<<"刪除了第一個結(jié)點(diǎn)!\n";
}
else{
p=find(head,k-1); //查找第k-1個結(jié)點(diǎn)，并由p指向該結(jié)點(diǎn)
if(p->next!=NULL){
p1=p->next;
p->next=p1->next;
delete p1;
cout<<"刪除了第"<<k<<"個結(jié)點(diǎn)!\n";
}
}
return head;
}
//插入一個結(jié)點(diǎn)，不改變鏈表上的升序關(guān)系
node *insert(node *head,int num)
{
node *p1,*p2,*p3;
p1=head;
p2=head->next;
while(!(((p1->data)<=num)&&((p2->data)>=num))){
p1=p1->next;
p2=p2->next;
}
p3=new node;
p3->data=num;
p1->next=p3;
p3->next=p2;
return head;
}
//測試函數(shù)
void main()
{
node *head;
int num;
head=creat_sort();
print(head);
cout<<"結(jié)點(diǎn)數(shù):"<<count(head)<<endl;
cout<<"輸入要刪除結(jié)點(diǎn)上的序號!\n";
cin>>num;
head=delete_k_node(head,num);
print(head);
cout<<"輸入要刪除結(jié)點(diǎn)上的整數(shù)!\n";
cin>>num;
head=delete_one_node(head,num);
print(head);
cout<<"輸入要插入的整數(shù)!\n";
cin>>num;
head=insert(head,num);
print(head);
deletechain(head);
}
/**********************************************
建立一條有序鏈表，請輸入數(shù)據(jù)，以-1結(jié)束:
9 8 6 5 4 3 2 1 -1
鏈表上各個結(jié)點(diǎn)的數(shù)據(jù)為：
1 2 3 4 5 6 8 9
結(jié)點(diǎn)數(shù):8
輸入要刪除結(jié)點(diǎn)上的序號!
1
刪除了第一個結(jié)點(diǎn)!
鏈表上各個結(jié)點(diǎn)的數(shù)據(jù)為：
2 3 4 5 6 8 9
輸入要刪除結(jié)點(diǎn)上的整數(shù)!
2
刪除了一個結(jié)點(diǎn)!
鏈表上各個結(jié)點(diǎn)的數(shù)據(jù)為：
3 4 5 6 8 9
輸入要插入的整數(shù)!
7
鏈表上各個結(jié)點(diǎn)的數(shù)據(jù)為：
3 4 5 6 7 8 9
已釋放鏈表的結(jié)點(diǎn)空間!
Press any key to continue
**************************************/

復(fù)制代碼

帳號		自動登錄	找回密碼
密碼			立即注冊

C++語言 線性表的插入和刪除

相關(guān)帖子

C++語言線性表的插入和刪除