本帖最后由 daming 于 2014-12-30 02:14 编辑
- #include<iostream.h>
- struct node
- {
- int data;
- node *next;
- };
- //建立一条升序链表 (尾插法:最后建立的结点是表头,故应降序输入)
- node *creat_sort()
- {
- node *p1,*head=NULL;
- int a;
- cout<<"建立一条有序链表,请输入数据,以-1结束:\n";
- cin>>a;
- while(a!=-1){
- p1=new node;
- p1->data=a;
- p1->next=head;
- head=p1;
- cin>>a;
- }
- return head;
- }
- //输出链表上各个结点的值
- void print(const node *head)
- {
- const node *p;
- p=head;
- cout<<"链表上各个结点的数据为:\n";
- while(p!=NULL){
- cout<<p->data<<'\t';
- p=p->next;
- }
- cout<<endl;
- }
- //删除链表上具有指定值的一个结点
- node *delete_one_node(node *head,int num)
- {
- node *p1,*p2;
- if(head==NULL){
- cout<<"链表为空,无结点可删!\n";
- return NULL;
- }
- if(head->data==num){
- p1=head;
- head=head->next;
- delete p1;
- cout<<"删除了一个结点!\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<<"删除了一个结点!\n";
- }
- else
- cout<<num<<"链表上没有找到要删除的结点!\n";
- }
- return head;
- }
- //释放链表的结点空间
- void deletechain(node *h)
- {
- node *p1;
- while(h){
- p1=h;
- h=h->next;
- delete p1;
- }
- cout<<"已释放链表的结点空间!\n";
- }
- //求链表的结点数
- int count(node *head)
- {
- int n;
- node *p;
- p=head;
- n=0;
- while(p!=NULL){
- n=n+1;
- p=p->next;
- }
- return n;
- }
- ////查找第k个结点
- node *find(node *head,int k)
- {
- int i;
- node *p;
- i=1;
- p=head;
- while(i<k){
- i++;
- p=p->next;
- }
- return p;
- }
- //删除链表上第K个结点
- node *delete_k_node(node *head,int k)
- {
- int j=1;
- node *p,*p1;
- if(head==NULL){
- cout<<"链表为空,无结点可删!\n";
- return NULL;
- }
- p=head;
- if(k==1){
- p=head;
- head=head->next;
- delete p;
- cout<<"删除了第一个结点!\n";
- }
- else{
- p=find(head,k-1); //查找第k-1个结点,并由p指向该结点
- if(p->next!=NULL){
- p1=p->next;
- p->next=p1->next;
- delete p1;
- cout<<"删除了第"<<k<<"个结点!\n";
- }
- }
- return head;
- }
- //插入一个结点,不改变链表上的升序关系
- 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;
- }
- //测试函数
- void main()
- {
- node *head;
- int num;
- head=creat_sort();
- print(head);
- cout<<"结点数:"<<count(head)<<endl;
- cout<<"输入要删除结点上的序号!\n";
- cin>>num;
- head=delete_k_node(head,num);
- print(head);
- cout<<"输入要删除结点上的整数!\n";
- cin>>num;
- head=delete_one_node(head,num);
- print(head);
- cout<<"输入要插入的整数!\n";
- cin>>num;
- head=insert(head,num);
- print(head);
- deletechain(head);
- }
- /**********************************************
- 建立一条有序链表,请输入数据,以-1结束:
- 9 8 6 5 4 3 2 1 -1
- 链表上各个结点的数据为:
- 1 2 3 4 5 6 8 9
- 结点数:8
- 输入要删除结点上的序号!
- 1
- 删除了第一个结点!
- 链表上各个结点的数据为:
- 2 3 4 5 6 8 9
- 输入要删除结点上的整数!
- 2
- 删除了一个结点!
- 链表上各个结点的数据为:
- 3 4 5 6 8 9
- 输入要插入的整数!
- 7
- 链表上各个结点的数据为:
- 3 4 5 6 7 8 9
- 已释放链表的结点空间!
- Press any key to continue
- **************************************/
复制代码
|