#define _CRT_SECURE_NO_DEPRECATE /*取消scanf,printf不安全之类的错误提示*/ #include <stdio.h> #include <stdlib.h> typedef struct node { int value; struct node* next; }listnode; listnode* Creat_List1(int nodenum, int *data); //最先进去的元素在最后面 listnode* Creat_List2(int nodenum, int *data); //最先进去的元素在最前面 int Get_Link_Element(listnode* head, int i); //取得头指针为head的链表中的第i个元素的值(包括第0个元素) void Insert_List(listnode* head, int a, int i); void Delet_List(listnode* head, int i); //删除第i个元素 listnode* Merge_TWO_Linklist(listnode *list1, listnode *list2);//合并两个有序链表 int main() { int data; listnode *linka, *linkb, *linkc, *linkd, *linke; linka = (listnode*)malloc(sizeof(listnode)); linkb = (listnode*)malloc(sizeof(listnode)); linkc = (listnode*)malloc(sizeof(listnode)); linkd = (listnode*)malloc(sizeof(listnode)); linke = (listnode*)malloc(sizeof(listnode)); int a[5] = { 1, 3, 5, 7, 9 }; int b[3] = { 2,2, 4 }; linka = Creat_List2(5, a); linkb = Creat_List2(3, b); Insert_List(linkb, 10, 1); Delet_List(linkb, 1); linkc=Merge_TWO_Linklist(linka, linkb); data = Get_Link_Element(linkb, 1); printf("%d ", data); } //新元素总是插入到头指针后面,结果就是原先的元素一直往后移 listnode* Creat_List1(int nodenum,int *data) { listnode *pc; //保存新节点 listnode *head; head = (listnode*)malloc(sizeof(listnode)); head->next = NULL; //先建立一个带头结点的单链表 /*开始插入元素*/ for (int i = 0; i < nodenum; i++) { pc = (listnode*)malloc(sizeof(listnode)); pc->value = data[i]; pc->next = head->next; head->next = pc; } return head; } //新元素插入到头指针前面,头指针一直往后移 listnode* Creat_List2(int nodenum, int *data) { listnode *pc; //保存新节点 listnode *head; listnode *r;//保存产生的链表 head = (listnode*)malloc(sizeof(listnode)); head->next = NULL; //先建立一个带头结点的单链表 r = head; /*开始插入元素*/ for (int i = 0; i < nodenum; i++) { pc = (listnode*)malloc(sizeof(listnode)); pc->value = data[i]; head->next = pc; pc->next = NULL; head = pc; } return r; } //取得头指针为head的链表中的第i个元素的值(包括第0个元素) int Get_Link_Element(listnode* head, int i) { /*创建一个扫描指针,让它指向第一个元素*/ listnode* pc; int j = 0; //计数 pc = (listnode*)malloc(sizeof(listnode)); pc = head->next; while (pc != NULL && j < i) //遍历 { pc = pc->next; j++; } if (pc == NULL || j > i) exit(-1); return pc->value; } /* *合并两个有序链表,把list2合并到list1 */ listnode* Merge_TWO_Linklist(listnode *list1, listnode *list2) { listnode *pc1, *pc2, *pc3,*list3; pc1 = (listnode*)malloc(sizeof(listnode)); pc2 = (listnode*)malloc(sizeof(listnode)); pc3 = (listnode*)malloc(sizeof(listnode)); pc1 = list1->next; pc2 = list2->next; pc3 = list1; list3 = pc3; while (pc1 != NULL && pc2 != NULL) { if (pc1->value <= pc2->value) { pc3->next = pc1; pc3 = pc3->next; pc1 = pc1->next; } else{ pc3->next = pc2; pc3 = pc3->next; pc2 = pc2->next; } } if (pc1 == NULL) pc3->next = pc2; if (pc2 == NULL) pc3->next = pc1; free(list2); return list3; } void Insert_List(listnode* head, int a, int i) { listnode *pc; listnode *s; pc = head->next;//令pc指向第一个元素 int j = 1; while (pc != NULL && j < i) { pc = pc->next; //pc后移动 j++; } if (pc == NULL) { printf("error "); exit(-1); } s = (listnode*)malloc(sizeof(listnode)); s->value = a; s->next = pc->next; pc->next = s; } //删除第i个元素 void Delet_List(listnode* head, int i) { listnode *temp = NULL; int j = 1; //计数 head = head->next; while (head != NULL && j < i) { head = head->next; j++; } if (head == NULL) { printf("error "); exit(-1); } temp = head->next; head->next = temp->next; //head = head->next->next; free(temp); }
#define _CRT_SECURE_NO_DEPRECATE #include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <stack> #include <stdio.h> #include <stdlib.h> using namespace std; struct ListNode { int value; ListNode *next; }; //创建一个只含头结点的链表 ListNode* CreatListHead() { ListNode* pHead = (ListNode*)malloc(sizeof(ListNode)); pHead->next = NULL; return pHead; } //插入节点到末尾 void AddToTail(ListNode** pHead, int Value) { //申请空间,构造新插入的节点 ListNode *pNew = (ListNode*)malloc(sizeof(ListNode)); pNew->value = Value; pNew->next = NULL; //如果原来的链表为空,则插入的节点作为头结点 if(*pHead == NULL) { *pHead = pNew; } else { //找到最后一个节点 ListNode *pNode = *pHead; //声明一个指针指向当前的头结点 while(pNode->next != NULL) { pNode = pNode->next; //节点后移,直到最后一个节点 } //插入新节点 pNode->next = pNew; } } void RemoveNode(ListNode** pHead, int value) { if(pHead == NULL || *pHead == NULL) return; ListNode* ToBeDeleted = NULL; //如果要删除的节点在链表头 if((*pHead)->value == value) { ToBeDeleted = *pHead; *pHead = (*pHead)->next; } else { //声明一个指针指向头节点 ListNode* pNode = *pHead; //遍历链表,知道找到要删除的节点 while(pNode->next != NULL && pNode->next->value != value) pNode = pNode->next; if(pNode->next != NULL && pNode->next->value == value) { ToBeDeleted = pNode->next; pNode->next = pNode->next->next; //删除节点 } if(ToBeDeleted != NULL) { free(ToBeDeleted); ToBeDeleted = NULL; } } } //递归方式从尾到头打印链表 void PrintListReversingly(ListNode *pHead) { if(pHead != NULL) { if(pHead->next != NULL) PrintListReversingly(pHead->next); } printf("%d ", pHead->value); } //栈方式从尾到头打印链表 void PrintListResversingly_Stack(ListNode *pHead) { std::stack<ListNode*> nodes; ListNode* pNode = pHead; while(pNode != NULL) { nodes.push(pNode); pNode = pNode->next; } while(!nodes.empty()) { pNode = nodes.top(); printf("%d ", pNode->value); nodes.pop(); } } int main() { int a[] = {1,2,3,4,5}; int size = sizeof(a) / sizeof(int); ListNode* pList = CreatListHead(); //包含空头结点的链表 ListNode* pList2 = NULL; AddToTail(&pList, 5); for(int i = 0; i < size; i++) { AddToTail(&pList2, a[i]); } RemoveNode(&pList2, 4); PrintListReversingly(pList2); PrintListResversingly_Stack(pList2); }