上一篇写单链表是带头结点的,但是其他这种写法的单链表中,头结点其实就不是那么必要了,因为我们的单链表结构体中增加了一项m_length
下面的不加头结点的单链表奉上
不带头结点的单链表结构体
-
#include <stdio.h>
-
#include <stdlib.h>
-
#include <stdbool.h>
-
#include <assert.h>
-
-
-
-
-
-
-
-
-
-
-
-
typedef int ElemType;
-
-
-
-
-
typedef struct LinkListNode
- {
- ElemType m_data;
- struct LinkListNode *m_next;
- }LinkListNode;
-
-
-
typedef struct LinkList
- {
- LinkListNode *m_head;
- int m_length;
- }LinkList;
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- LinkList* CreateLinkList(void)
- {
- LinkList *list = NULL;
- if((list = (LinkList *)malloc(sizeof(LinkList))) == NULL)
- {
- fprintf(stderr, "not enough memory when CREATE LIST...\n");
- exit(EXIT_FAILURE);
- }
-
- InitLinkList(list);
-
- return list;
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
void InitLinkList(LinkList *list)
- {
- list->m_head = NULL;
- list->m_length = 0;
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- LinkList* DestroyLinkList(LinkList *list)
- {
- ClearLinkList(list);
- FinitLinkList(list);
- if(list != NULL)
- {
- free(list);
- list = NULL;
- }
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
void FinitLinkList(LinkList *list)
- {
- assert(list->m_head == NULL);
-
- list->m_length = -1;
- }
-
-
-
-
-
-
-
-
-
-
-
-
void ClearLinkList(LinkList *list)
- {
- while(list->m_head != NULL)
- {
- DeleteNode(list, 0);
- }
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- LinkListNode* FindPosNode(LinkList *list, int position)
- {
- assert(list != NULL);
- assert(position >= 0 && position < list->m_length);
-
- LinkListNode *pNode = list->m_head;
- int pos = 0;
-
- while(pNode != NULL && pos < position)
- {
- pNode = pNode->m_next;
- pos++;
- }
-
- if(pNode == NULL || pos < position)
- {
- return NULL;
- }
- else
- {
-
#ifdef DEBUG
- printf("Find the %d point SUCCESS...[%p]\n", position, pNode);
-
#endif // DEBUG
- return pNode;
- }
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- LinkListNode *FindPrevNode(LinkList *list, LinkListNode *currNode)
- {
- assert(list != NULL);
- assert(currNode != NULL);
-
- LinkListNode *pNode = list->m_head;
-
- while(pNode->m_next != NULL && pNode->m_next != currNode)
- {
- pNode = pNode->m_next;
- }
-
- if(pNode->m_next == currNode)
- {
- return pNode;
- }
- else
- {
- return NULL;
- }
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
int IsNodeInList(LinkList *list, LinkListNode *node)
- {
- assert(list != NULL);
-
- LinkListNode *pNode = list->m_head;
- int pos = 0;
-
- while(pNode != NULL && pNode != node)
- {
- pNode = pNode->m_next;
- pos++;
- }
-
- if(pNode != node)
- {
- return -1;
- }
- else
- {
-
#ifdef DEBUG
- printf("Find the [%p] point in the first %d pointer of the list...\n", fNode, pos);
-
#endif // DEBUG
- return pos;
- }
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- LinkListNode* InsertNode(LinkList *list, int position, ElemType data)
- {
- assert(list != NULL);
- assert(position >=0 && position < list->m_length + 1);
-
- LinkListNode *prevNode = NULL;
- LinkListNode *newNode = NULL;
-
-
- if((newNode = (LinkListNode *)malloc(sizeof(LinkListNode))) == NULL)
- {
- fprintf(stderr, "not enough memeory\n");
- exit(EXIT_FAILURE);
- }
- else
- {
- newNode->m_data = data;
- newNode->m_next = NULL;
- }
-
-
- if(position == 0)
- {
- if(list->m_head == NULL)
- {
- list->m_head = newNode;
- }
- else
- {
-
- newNode->m_next = list->m_head;
- list->m_head = newNode;
- }
- }
- else
- {
- prevNode = FindPosNode(list, position - 1);
-
- newNode->m_next = prevNode->m_next;
- prevNode->m_next = newNode;
- }
-
- list->m_length++;
-
-
#ifdef DEBUG
- printf("Insert the value %d into list at position %d...\n", data, position);
-
#endif // DEBUG
-
-
- return newNode;
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- LinkListNode *AddNode(LinkList *list, LinkListNode *prevNode, ElemType data)
- {
- assert(prevNode != NULL);
-
- LinkListNode *newNode = NULL;
- if((newNode = (LinkListNode *)malloc(sizeof(LinkListNode))) == NULL)
- {
- fprintf(stderr, "not enough memeory\n");
- exit(EXIT_FAILURE);
- }
-
-
-
- newNode->m_data = data;
- newNode->m_next = NULL;
- if(prevNode == (LinkListNode *)list)
- {
- if(list->m_head == NULL)
- {
- list->m_head = newNode;
- }
- else
- {
-
- newNode->m_next = list->m_head;
- list->m_head = newNode;
- }
- }
- else
- {
-
- newNode->m_next = prevNode->m_next;
- prevNode->m_next = newNode;
- }
- list->m_length++;
-
-
#ifdef DEBUG
- printf("The new node is inserted after point pointer[%p]\n", pNode);
-
#endif // DEBUG
- return newNode;
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- ElemType DeleteNode(LinkList *list, int position)
- {
- assert(list != NULL);
- assert(position >=0 && position < list->m_length);
-
- LinkListNode *delNode = NULL;
- ElemType delElem = -1;
- if(position == 0)
- {
- delNode = list->m_head;
-
- if(list->m_head->m_next == NULL)
- {
- list->m_head = NULL;
- }
- else
- {
- list->m_head = delNode->m_next;
- }
- }
- else
- {
- LinkListNode *pNode = FindPosNode(list, position - 1);
-
-
- delNode = pNode->m_next;
- pNode->m_next = delNode->m_next;
- }
- delElem = delNode->m_data;
- free(delNode);
- list->m_length--;
-
#ifdef DEBUG
- printf("Delete the list in the first %d node...\n", position);
-
#endif // DEBUG
- return delElem;
- }
-
-
-
-
-
-
-
-
-
-
-
-
- ElemType SubNode(LinkList *list, LinkListNode *prevNode)
- {
- assert(list != NULL);
- assert(prevNode != NULL);
- assert(IsNodeInList(list, prevNode) != -1);
-
- LinkListNode *delNode = NULL;
- ElemType delElem = -1;
-
- if(prevNode == list)
- {
- delNode = list->m_head;
-
- if(list->m_head->m_next == NULL)
- {
- list->m_head = NULL;
- }
- else
- {
- list->m_head = delNode->m_next;
- }
- }
- else
- {
-
- delNode = prevNode->m_next;
- prevNode->m_next = delNode->m_next;
- }
- delElem = delNode->m_data;
- free(delNode);
-
- list->m_length--;
- list->m_head->m_data--;
-
- return delElem;
- }
-
-
-
-
-
-
-
-
-
-
-
-
- ElemType DeleteCurrNode(LinkList *list, LinkListNode *currNode)
- {
- assert(list != NULL);
- assert(currNode != NULL);
- assert(IsNodeInList(list, currNode) != -1);
-
- ElemType delElem = -1;
- LinkListNode *delNode = NULL;
-
- if(currNode == list->m_head)
- {
- delNode = list->m_head;
-
- if(list->m_head->m_next == NULL)
- {
- list->m_head = NULL;
- }
- else
- {
- list->m_head = delNode->m_next;
- }
- }
- else
- {
- if(currNode->m_next != NULL)
- {
-
- delNode = currNode->m_next;
- currNode->m_next = delNode->m_next;
-
-
- delElem = currNode->m_data;
- currNode->m_data = delNode->m_data;
- }
- else
- {
-
- delNode = currNode;
-
- LinkListNode *prevNode = FindPrevNode(list, currNode);
- prevNode->m_next = NULL;
- }
- }
- free(delNode);
- list->m_length--;
- return delElem;
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
void ShowList(LinkList *list)
- {
- printf("there are %d data in list\n", list->m_length);
-
- LinkListNode *pNode = list->m_head;
-
- while(pNode != NULL)
- {
- printf("%d ", pNode->m_data);
- pNode = pNode->m_next;
- }
- printf("\n");
-
-
-
-
-
-
-
-
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
void SetNode(LinkList *list, int position, ElemType data)
- {
- LinkListNode *pNode = FindPosNode(list, position);
-
- pNode->m_data = data;
- }
-
-
-
-
-
-
-
-
-
-
-
-
- ElemType GetNode(LinkList *list, int position)
- {
- LinkListNode *pNode = FindPosNode(list, position);
-
- return pNode->m_data;
- }
-
-
-
-
-
-
-
-
-
-
-
-
int LengthLinkList(LinkList *list)
- {
- return list->m_length;
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
bool IsEmptyLinkList(LinkList *list)
- {
- return (list->m_length == 0);
-
- }
-
-
-
-
-
#define LIST_SIZE 7
-
-
int main(void)
- {
- int pos;
-
- printf("TEST 1...\n");
- LinkList *plist = CreateLinkList( );
- for(int pos = 0; pos < LIST_SIZE; pos++)
- {
- InsertNode(plist, pos, pos + 1);
- printf("HEAD = %p\n", plist->m_head);
- }
- ShowList(plist);
-
- DeleteNode(plist, 0);
- ShowList(plist);
- DeleteNode(plist, 1);
- ShowList(plist);
-
- ClearLinkList(plist);
- ShowList(plist);
- DestroyLinkList(plist);
- plist = NULL;
-
- printf("\n\nTEST 2...\n");
- LinkList list;
- InitLinkList(&list);
- for(int pos = 0; pos < LIST_SIZE; pos++)
- {
- InsertNode(&list, pos, pos + 1);
- }
- ShowList(&list);
- ClearLinkList(&list);
-
- ShowList(&list);
-
- printf("\n\nTEST 3...\n");
- LinkListNode *prevNode = NULL;
- LinkListNode *addNode = NULL;
- prevNode = InsertNode(&list, 0, 1);
-
- for(int pos = 1; pos < LIST_SIZE; pos++)
- {
- if((addNode = AddNode(&list, prevNode, pos + 1)) != NULL)
- {
- prevNode = addNode;
- }
- }
-
-
-
-
-
-
-
-
-
- ShowList(&list);
- while(IsEmptyLinkList(&list) != true)
- {
- DeleteCurrNode(&list, list.m_head);
- }
- ShowList(&list);
-
- return EXIT_SUCCESS;
- }
转载:http://blog.csdn.net/gatieme/article/details/42527709