// Link.cpp : 定义控制台应用程序的入口点。 //单链表 #include "stdafx.h" #include <iostream> #include <complex> using namespace std; typedef struct node { int data;//节点内容 node *next;//下一个节点 }node; //创建单链表 node *create(){ node *head,*p,*q; int i=0; //单链表中数据的个数 int a=-1; head=new node;//创建头节点 head->next=NULL; while (1) { cout<<"please input the data(input -1,quit):"; cin>>a; if (-1==a) //如果输入的是-1,退出 { break; } p=new node; p->data=a; p->next=NULL;//链表的最后一个指针为NULL if (++i==1) //链表只有一个元素 { //连接到head的后面 head->next=p; } else{ q->next=p;//连接到链表尾端 } q=p;//q指向末节点 } return head; } //单链表的测长 int length(node *head){ int len=0; node *p=head->next; while (p!=NULL){//遍历链表 ++len; p=p->next; } return len; } //打印单链表 void print(node *head){ node *p=head->next; int index=0; if (p==NULL)//链表为NULL { cout<<"Link is empty!"<<endl; getchar(); return; } while (p!=NULL)//遍历链表 { cout<<"The "<<++index<<"th node is :"<<p->data<<endl;//打印元素 p=p->next; } } //查找单链表pos位置的节点,返回节点指针 //pos 从o开始,0 返回head节点 node *search_node(node *head,int pos){ node *p=head->next; if (pos<0)//pos 位置不正确 { cout<<"incorrect position to search node"<<endl; return NULL; } if (0==pos)//在head位置,返回head { return head; } if (p==NULL) { cout<<"Link is empty!"<<endl; return NULL; } while (--pos) { if ((p=p->next)==NULL) { cout<<"incorrect position to search node"<<endl; break; //超出链表返回 } } return p; } //单链表节点插入 //在单链表中某个位置(第pos个节点)后面插入节点,返回链表头指针 //pos 从0开始计算,0表示插入head节点后面 node *insert_node(node *head,int pos,int data){ node *p=new node; p->data=data; p->next=NULL; node *q=head; if (pos==0) { p->next=q->next; q->next=p; } while (pos) { q=q->next; --pos; } if (q!=NULL) { p->next=q->next;//p指向原pos节点的后一个节点 q->next=p; //p插入到pos的后面 } return head; } //删除单链表的pos位置的节点,返回链表头指针 //pos从1开始计算,1表示删除head后的第一个节点 node *delete_node(node *head,int pos){ node *q=head->next; node *p=NULL; if (q==NULL) { cout<<"Link is empty!"<<endl; return NULL; } while (--pos) { q=q->next;//得到位置pos的节点 } if (q!=NULL && q->next!=NULL) { p=q->next; q->next=p->next; delete p; } return head; } int _tmain(int argc, _TCHAR* argv[]) { node *head=create();//创建单链表 cout<<"Length:"<<length(head)<<endl;//测量单链表长度 head=insert_node(head,2,5); //在第2个节点后面插入5 cout<<"insert integer 5 after 2th node:"<<endl; print(head); //打印单链表 head=delete_node(head,2);//删除第2个节点 cout<<"delete the 3th node:"<<endl; print(head); cout<<"search the 3th node:"<<endl; node *p=search_node(head,3); //查找第3个节点 if (p!=NULL) { cout<<p->data<<endl; } system("pause"); delete [] head; return 0; }