单链表的基本操作实现

wapysun

浏览: 22610111 次
性别:
来自: 杭州

最近访客更多访客>>

devcang

hunankeda110

辽东小小

apex53

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

2012-06 ( 77)
2012-05 ( 587)
2012-04 ( 177)
更多存档...

#include #include using namespace std; typedef struct node { int data; struct node *next; }slink; void create(slink *&head) { head = new slink; head->next = NULL; } void getlen(slink *head, unsigned &len) { slink *p; p = head; while (p!= NULL) { ++len; p = p->next; } } void print(slink *head) { slink *p; p = head; while ( p != NULL) { cout << p->data << "\t"; p = p->next; } } /*slink* insert(slink *head, int data, int posi) //按位置插入 { slink* p = head; slink* insert; if (head == NULL) //当没有数据时，插入头链表 { insert = new slink; insert -> data = data; insert -> next = NULL; head = insert; return head; } else { for ( int a = 0; a < posi - 1; a++) { p = p -> next; } if (0 == posi) { insert = new slink; insert -> data = data; insert -> next = p; head = insert; return head; } else { insert = new slink; insert -> data = data; insert-> next = p -> next; p -> next = insert; return head; } } return head; }*/ slink* insert(slink *head, int data) //按从小到大顺序插入 { slink *p0, *p1, *p2; p1 = head; p0 = new slink; p0 -> data = data; while( p0->data > p1->data && p1->next != NULL) { p2 = p1; p1 = p1 -> next; } if (p0 -> data <= p1 ->data) { if (head == p1) { p0 -> next = p1; head = p0; } else { p0->next = p1; p2->next = p0; // p0 -> next = p2 -> next; //和上面两语句等效 // p2 -> next = p0; } } else { p1 -> next = p0; p0 -> next = NULL; } return head; } slink* search(slink *head, int sdata) { slink* p = NULL; while (head != NULL ) { if (head -> data == sdata) { p = head; return p; } else { head = head -> next; continue; } } return p; } slink* del(slink *head, int deldata) { slink *p = head; slink *del = NULL; while ( p != NULL ) { if ( p -> data == deldata ) { if ( p == head ) //当删除的结点为头结点时 { head = head -> next; delete p; //在堆中删除 return head; } else { del -> next = p -> next; delete p; return head; } } del = p; p = p -> next; } cout<<"删除失败，没有找到节点"< next == NULL) { return head; } p = head; for ( int j = 1; j < length; ++j) { p = head; for (int i = 0; i < length - j; ++i) { if (p->data < p->next->data) //从大到小排序 { temp = p->data; p->data = p->next->data; p->next->data = temp; } p = p->next; } } return head; } slink* reverse(slink* head) { /* slink *preNode,*curNode,*nextNode; if(head==NULL) return NULL;//空链表 if(head->next == NULL) return head;//仅一个元素 curNode = head;preNode=NULL;//初始化 while(curNode) { nextNode = curNode->next;//先记录下一个结点 curNode->next = preNode;//改变链表方向（逆置） preNode = curNode;//将当前结点作为下一次循环的前一个结点 curNode = nextNode;//向后推移一个结点 } return preNode;//当遍历完链表后curNode应该为空，此时preNode就是逆置后链表头(head) */ slink *p1, *p2, *p3; if ( head == NULL || head -> next == NULL) { return head; } p1 = head, p2 = p1 -> next; while (p2) { p3 = p2 -> next; p2 -> next = p1; p1 = p2; p2 = p3; } head -> next = NULL; head = p1; return head; } slink* searchmid(slink* head, slink *mid) { slink *temp = head; slink *p = head; while ( p->next != NULL && p->next->next != NULL ) //此处两个逻辑表达式顺序不能交换 { p = p->next->next; temp = temp->next; mid = temp; } return mid; } int main() { int choose; unsigned len = 0; int isExit = 1; slink *head = NULL; create(head); //创建链表 head -> data = 0; while(isExit) { cout << endl; cout << "****************************" << endl; cout << "* 1、退出 *" << endl; cout << "* 2、插入数据 *" << endl; cout << "* 3、查询数据 *" << endl; cout << "* 4、输出链表 *" << endl; cout << "* 5、求链表长度 *" << endl; cout << "* 6、删除链表 *" << endl; cout << "* 7、排序 *" << endl; cout << "* 8、链表逆置 *" << endl; cout << "* 9、搜索链表中间结点 *" << endl; cout << "****************************" << endl; cout << "Please enter your choose(1、2、3、4、5、6、7、8): " << endl; cin >> choose; switch(choose) { case 1: { isExit = 0; slink *p; while (head != NULL) { p = head; head = head -> next; delete p; } cout << "bye!" << endl; } break; case 2: { /*int data; //按位置插入 int posi; cout << "输入要插入的数据:" << endl; cin >> data; cout << "输入插入位置: " << endl; cin >> posi; head = insert(head, data, posi); */ int data; //按大小插入 cout << "\n输入要插入的数据:" << endl; cin >> data; head = insert(head, data); break; } case 3: { slink* result; int sdata; cout << "\n输入查询数据:" << endl; cin >> sdata; result = search(head, sdata); if ( result != NULL ) { cout << "查询结果: " << result -> data << endl; } else { cout << "search false" << endl; } break; } case 4: { print(head); break; } case 5: { getlen(head, len); cout << "\n该链表长度：" << len << endl; break; } case 6: { cout << " \nbefore delete: "; print(head); slink *delhead; int deldata; cout<< "\n输入要删除节点的数据:" << endl; cin >> deldata; delhead = del(head, deldata); cout << "\nafter delete " << endl; print(delhead); break; } case 7: { print(head); sort(head); cout << endl; print(head); break; } case 8: { print(head); head = reverse(head); cout << endl; print(head); break; } case 9: { slink *middata = NULL; middata = searchmid(head, middata); print(head); cout << " \nmiddata: " << middata->data << endl; } default: break; } } return 0; }

分享到：