单链表的增删查逆置倒数第k个节点等问题

对于单链表而言，它没有双链表那么复杂，它只有头节点，尾节点，节点数据，后继指针。在下面本人实现了单链表的增删插查改。 #include<stdio.h> #include<assert.h> #include<malloc.h> #include<stdlib.h> typedef int Datatype; typedef struct SListNode { Datatype data; struct SListNode*next; }SListNode; void PushBack(SListNode*&pHead, Datatype x); void PopBack(SListNode *&pHead); void PrintSlist(SListNode *&PHead); void PushFrot(SListNode*&pHead,Datatype x); void PopFront(SListNode*&pHead); SListNode *Find(SListNode*pHead, Datatype x); //void Insert(SListNode*pHead, Datatype pos, Datatype x); void Insert(SListNode*pHead, Datatype x); void Erase(SListNode*&pHead,SListNode *pos ); void InsertNoNode(SListNode *pos, Datatype x); SListNode* _BuyNode(Datatype x) { SListNode *temp = (SListNode*)malloc(sizeof(SListNode)); temp->data = x; temp->next = NULL; return temp; } void PushBack(SListNode*&pHead, Datatype x) { //1 空 2 不为空 if (pHead == NULL) { pHead = _BuyNode(x); } else { SListNode *tail = pHead; while (tail->next != NULL) { tail = tail->next; } tail->next = _BuyNode(x); } } void PopBack(SListNode *&pHead) { //1空 2 一个节点 3 多个节点 if(pHead == NULL) { return; } else if (pHead->next == NULL) { free(pHead); pHead = NULL; } else{ SListNode *tail = pHead; SListNode *tem = NULL; while (tail->next != NULL) { tem = tail; tail = tail->next; } free(tail); tem->next = NULL; } } void PrintSlist(SListNode *&PHead) //打印链表 { SListNode*cur = PHead; while (cur!=NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); } void PushFrot(SListNode*&pHead, Datatype x) //头插 { if (pHead == NULL) { pHead = _BuyNode(x); } else { SListNode *tmp = _BuyNode(x); tmp->next = pHead; pHead = tmp; } } void PopFront(SListNode*&pHead) //单链表头删 { //1 空 //2 一个结点 //3 一个以上的节点 if (pHead == NULL) { return; } else if(pHead->next == NULL) { free(pHead); pHead = NULL; } else { SListNode *tmp = pHead; pHead = pHead->next; free(tmp); } } SListNode *Find(SListNode*pHead, Datatype x) //查找节点 { //assert(pHead); SListNode *tail = NULL;//当前指针 Datatype tmp ; //保存节点数据 if (pHead->data == x) { return pHead; } else { tail=pHead->next; while (tail!= NULL) { tmp = tail->data; if (tmp == x) //把节点数据与要查找的数比较 { return tail; //返回所要查找结点的地址 } else { tail =tail->next; } } printf("没有查到该数据！\n"); } } void Insert(SListNode*pos, Datatype x) ////在指定节点插入数据 { assert(pos); SListNode *tmp = _BuyNode(x); tmp->next = pos->next; pos->next = tmp; } void Erase(SListNode *&pHead,SListNode *pos) //删除指定位置的节点 { assert(pos); assert(pHead); if (pHead == pos) { pHead = pHead->next; free(pos); return; } SListNode *prv = pHead; while (prv) { if (prv->next == pos) { prv->next = pos->next; free(pos); break; } prv = prv->next; } } //删除一个无头单链表 void DelNoNode(SListNode *pos) { assert(pos); assert(pos->next); SListNode *del = pos->next; SListNode *next = del->next; pos->data = del->data; pos->next = next; free(del); } //在无头单链表的一个非头节点前插入一个节点 void InsertNoNode(SListNode *pos, Datatype x) { assert(pos); //assert(pos->next); //1 种方法 //Datatype temp = 0; //SListNode *behind = pos; //SListNode*prv =_BuyNode(x); //SListNode *next = behind->next; //pos->next = prv; //prv->next = next; //temp = pos->data; //pos->data = prv->data; //prv->data = temp; //2 种方法 SListNode*prv = _BuyNode(pos->data); prv->next = pos->next; pos->next = prv; pos->data = x; } //查找中间节点 SListNode *FindmidNode(SListNode *phead) { SListNode *fast = phead; SListNode *slow = phead; while (fast&&fast->next) { fast = fast->next->next; slow = slow->next; } return slow; } //找倒数第k个节点 SListNode *FindkNode(SListNode *phead, int k) { SListNode *fast = phead; SListNode *slow = phead; /*for (int i = 1; i<=k-1; i++) { fast = fast->next; } while (fast->next) { slow = slow->next; fast = fast->next; }*/ while (fast&&k--) { fast= fast->next; if (fast == NULL) return NULL; } while (fast) { slow = slow->next; fast = fast->next; } return slow; } //从尾到头打印链表 void PrintTailToHead(SListNode*phead) { if (phead) { PrintTailToHead(phead->next); printf("%d ", phead->data); } } // SListNode *Reverse(SListNode *phead)//单链表的逆置 { SListNode *cur = phead; SListNode *newhead = NULL; while (cur) { SListNode*tmp =cur; cur = cur->next; tmp->next =newhead; newhead = tmp; } return newhead; } void test1() { SListNode*list = NULL; PushBack(list, 1); PushBack(list, 3); PushBack(list, 2); PushBack(list, 4); PushBack(list, 6); PrintSlist(list); } void test2() { SListNode*list = NULL; PushBack(list, 1); PushBack(list, 2); PushBack(list, 3); PushBack(list, 4); PushBack(list, 5); PushBack(list, 6); PushBack(list, 7); PrintSlist(list); //Find(list, 4); //Insert(list,7, 8); SListNode *pos = Find(list, 1); Erase(list,pos ); PrintSlist(list); } void test3() { SListNode*list = NULL; PushBack(list, 1); PushBack(list, 2); PushBack(list, 3); PushBack(list, 4); PushBack(list, 5); PushBack(list, 6); PushBack(list, 7); PrintSlist(list); SListNode *pos = Find(list ,7); Insert(pos, 2); PrintSlist(list); } void test4() { SListNode*list = NULL; PushBack(list, 1); PushBack(list, 2); PushBack(list, 3); PushBack(list, 4); PushBack(list, 5); PushBack(list, 6); PushBack(list, 7); PrintSlist(list); /*SListNode *pos = list; DelNoNode(pos);*/ SListNode *pos = Find(list,1); InsertNoNode(pos, 9); PrintSlist(list); } void test5() { SListNode *list = NULL; PushBack(list, 1); PushBack(list, 8); PushBack(list, 2); PushBack(list, 3); PushBack(list, 4); PushBack(list, 5); PrintSlist(list); //SListNode*pos = FindmidNode(list); SListNode*pos =FindkNode(list, 5); printf("%d\n", pos->data); //PrintSlist(list); } void test6() { SListNode*list = NULL; PushBack(list, 1); PushBack(list, 3); PushBack(list, 2); PushBack(list, 4); PushBack(list, 6); // SListNode*pos=Reverse(list); PrintTailToHead(pos); } int main() { //test1(); test6(); system("pause"); return 0; }

单链表的增删查 逆置 倒数第k个节点等问题

相关阅读