#include<iostream> #include<cstdio> #include<cstdlib> using namespace std; typedef struct NodeType { char elem; struct NodeType *next; }Node; typedef struct DNodetype { char elem; struct DNodetype *prev; struct DNodetype *next; }DNode; /*创建单链表*/ Node *CreateList(Node *head) { if(NULL == head) { head = (Node *)malloc(sizeof(Node)); head->next = NULL; } Node *current = head, *temp; char ch; while(1) { cout<<"input elem(end of by '#'): "; cin>>ch; if('#' == ch) break; temp = (Node *)malloc(sizeof(Node)); temp->elem = ch; temp->next = NULL; current->next = temp; current = temp; } return head; } /*创建双链表*/ DNode *CreateDlist(DNode *head) { if(NULL == head) { head = (DNode *)malloc(sizeof(DNode)); head->next = NULL; } DNode *current = head, *temp; char ch; while(1) { cout<<"input elem: "; cin>>ch; if('#' == ch) break; temp = (DNode *)malloc(sizeof(DNode)); temp->elem = ch; temp->next = NULL; current->next = temp; temp->prev = current; current = temp; } return head; } /*创建循环单链表*/ Node *CycleList(Node *head) { if(NULL == head) { head = (Node *)malloc(sizeof(Node)); head->next = NULL; } Node *current = head, *temp; char ch; while(1) { cout<<"input elem(end of by '#'): "; cin>>ch; if('#' == ch) break; temp = (Node *)malloc(sizeof(Node)); temp->elem = ch; temp->next = NULL; current->next = temp; current = temp; } current->next = head; return head; } /*打印单链表*/ void PrintList(Node *head) { int n = 0; Node *current = head->next; cout<<"List are: "; while(NULL != current) { cout<<current->elem<<' '; current = current->next; } cout<<endl; } /*在单链表的末尾插入元素*/ void *InsertNode(Node *head, char elem) { if(NULL == head) return head; Node *current = head->next; Node *prev = head; Node *temp; while(NULL != current) { prev = current; current = current->next; } temp = (Node *)malloc(sizeof(Node)); temp->elem = elem; temp->next = NULL; prev->next = temp; return head; } /*删除单链表中某个元素*/ Node *DelNode(Node *head, char elem) { if(NULL == head || NULL == head->next) return head; Node *prev = head, *current = head->next; while(NULL != current) { if(current->elem == elem) { prev->next = current->next; free(current); return head; } prev = current; current = current->next; } return head; } /*单链表逆置*/ Node *ReverseList(Node *head) { if(NULL == head || NULL == head->next || NULL == head->next->next) return head; Node *current = head->next, *temp; head->next = NULL; while(NULL != current) { temp = current->next; current->next = head->next; head->next = current; current = temp; } return head; } /*求单链表的中间节点*/ Node *MiddleList(Node *head) { if(NULL == head || NULL == head->next) return head; Node *middle = head, *last = head; while(NULL != last->next) { last = last->next; if(NULL != last->next) last = last->next; middle = middle->next; } return middle; } /*合并有序单链表*/ Node *MergeList(Node *h1, Node *h2) { if(NULL == h1 || NULL == h2 || NULL == h2->next) return h1; if(NULL == h1->next) return h2; Node *curr1, *curr2, *prev1, *temp; prev1 = h1; curr1 = h1->next; curr2 = h2->next; temp = h2; while(curr2) { while(curr1 && curr1->elem < curr2->elem) { prev1 = curr1; curr1 = curr1->next; } temp = curr2->next; prev1->next = curr2; curr2->next = curr1; curr1 = curr2; curr2 = temp; } return h1; } /*判断链表是否有环*/ int isCycleList(Node *head) { if(NULL == head || NULL == head->next) return 0; Node *current = head; while(current) { if(current->next == head) return 1; current = current->next; } return 0; } int main() { //freopen("in.txt", "r", stdin); //Node *head = NULL; //Node *head2 = NULL; //head = (Node *)malloc(sizeof(Node)); //head = CreateList(head); //PrintList(head); //head2 = CreateList(head2); //PrintList(head2); //ReverseList(head); //PrintList(head); //InsertNode(head, '8'); //PrintList(head); //DelNode(head, 'l'); //PrintList(head); //head2 = CycleList(head2); //PrintList(head2); //printf("%c\n", MiddleList(head)->elem); //PrintList(MergeList(head, head2)); //printf("%d\n", isCycleList(head)); return 0; }