用C语言编程（对链表的操作）

(1)用头插法（或尾插法）建立带头结点的单链表；

(2)对已建立的单链表实现插人、删除、查找等基本操作。

最近怎么都在问这种问题了？

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

#define HEAD struct listhead
#define NODE struct listnode

void createList (HEAD *);
int insertNode (HEAD *, NODE *, int);
int emptyList (HEAD *);
int getNext (HEAD *, int, int *);
void printList (HEAD *);
void destroyList (HEAD *);
char menu();
void removeNode (HEAD *, int);
void deleteNode (HEAD *, NODE *, NODE *, int);
int searchList (HEAD *, NODE **, NODE **, int);
int getdata();

HEAD
{
int count;
NODE *pos;
NODE *head;
};

NODE
{
int data;
NODE *link;
};

void createList (HEAD *list)
{
list->count = 0;
list->pos = NULL;
list->head = NULL;
}

int getdata()
{
int InsertData;
printf("\nEnter the key to be inserted:");
scanf("%d", &InsertData);
return InsertData;
}

int insertNode (HEAD *list, NODE *pPre, int dataIn)
{
NODE *pNew;
pNew = (NODE *)malloc(sizeof(NODE));

if (pNew == NULL)
return 0;

pNew->data = dataIn;
if (pPre == NULL)
{
pNew->link = list->head;
list->head = pNew;
}
else
{
pNew->link = pPre->link;
pPre->link = pNew;
}
list->count ++;
return 1;
}

int emptyList(HEAD *list)
{
return (list->count == 0);
}

int getNext(HEAD *list, int fromWhere, int *dataOut)
{
int success;
if (fromWhere == 0)
if (emptyList(list) == 1)
success = 0;
else
{
list->pos = list->head;
*dataOut = list->pos->data;
success = 1;
}
else
if (list->pos->link == NULL)
success = 0;
else
{
list->pos = list->pos->link;
*dataOut = list->pos->data;
success = 1;
}
return success;
}

void printList(HEAD *list)
{
int count, moreData;
int dataPtr;
if (emptyList(list) == 1)
printf("\nNo data in the list.\n");
else
{
printf("\n\nBegin data print...\n");
count = 0;
moreData = getNext(list, 0, &dataPtr);
while (moreData == 1)
{
count ++;
printf(" %d: %d\n", count, dataPtr);
moreData = getNext(list, 1, &dataPtr);
}
printf("End data print...\n");
}
}

void destroyList (HEAD *list)
{
NODE *dltPtr;
while (list->count > 0)
{
dltPtr = list->head;
list->head = dltPtr->link;
list->count --;
free(dltPtr);
}
list->pos = NULL;
}

char menu()
{
int valid, choice;
printf("\n---Menu---\n");
printf("\n");
printf("A: Add new data\n");
printf("D: Delete data\n");
printf("P: Print List\n");
printf("Q: Quit\n");
printf("\n");
valid = 0;
while (valid == 0)
{
printf("Enter your choice:");
choice = getch();
printf("\n");
if (strchr("AaDdPpQq", choice) != NULL)
valid = 1;
else
printf("\nInvalid choice. Choices are <A, D, P, Q>:");
}
return choice;
}

void removeNode (HEAD *list, int dataOut)
{
int found;
NODE *pPre, *pLoc;
found = searchList(list, &pPre, &pLoc, dataOut);
if (found)
{
deleteNode(list, pPre, pLoc, dataOut);
printf("Data:%d was removed !",dataOut);
}
else
printf("Data:%d not found, remove node fail!",dataOut);
}

void deleteNode (HEAD *list, NODE *pPre, NODE *pLoc, int dataOut)
{
dataOut = pLoc->data;
if (pPre == NULL)
list->head = pLoc->link;
else
pPre->link = pLoc->link;
list->count --;
free(pLoc);
}

int searchList(HEAD *list, NODE **pPre, NODE **pLoc, int target)
{
*pPre = NULL;
*pLoc = list->head;
while (*pLoc != NULL && target != (*pLoc)->data)
{
*pPre = *pLoc;
*pLoc = (*pLoc)->link;
}
if (*pLoc == NULL)
return 0;
else if (target == (*pLoc)->data)
return 1;
else
return 0;
}

void main()
{
HEAD *list1;
NODE *pPre, *pLoc;
int dataIn;
char option;
int deleteKey;
clrscr();
list1 = (HEAD *)malloc(sizeof(HEAD));
createList(list1);
option = ' ';
while (strchr("Qq", option) == NULL)
{
option = menu();
switch (option)
{
case 'a':
case 'A':
dataIn = getdata();
insertNode(list1, NULL, dataIn);
break;
case 'd':
case 'D':
printf("\nEnter the key to be deleted:");
scanf("%d", &deleteKey);
removeNode(list1, deleteKey);
break;
case 'p':
case 'P':
printList(list1);
break;
}
printf("\n");
}
destroyList(list1);
printf("\nPress any key to return...");
getch();
}

前几天写的，幸好还没删，基本符合你的要求 #include <stdio.h> #include <stdlib.h> typedef struct _list { int val; struct _list* next; } *node, list; // 在pos位置之后插一个节点，pos = NULL就是头插，pos = 新插入的节点就是尾插 node insert( node* head, node pos, int val ) { node tmp; tmp = ( node )malloc( sizeof( list ) ); tmp->val = val; tmp->next = pos ? pos->next : *head; return ( pos ? pos->next : *head ) = tmp; } // 查找值为n的节点 node find( node head, int n ) { if ( !head ) return NULL; while ( head->val != n ) { head = head->next; } return head; } // 从数组简单构造一个链表 node create( int* beg, int* end ) { node head, t; head = t = NULL; while ( beg != end ) { t = insert( &head, t, *beg++ ); } return head; } // 删除节点n void remove( node* head, node n ) { node prev, next; prev = next = *head; while ( next != n ) { prev = next; next = next->next; } if ( prev == *head ) { *head = next->next; } else { prev->next = next->next; } free( next ); } // 遍历输出各个节点的值 void print( node head ) { while ( head ) { printf( "%d ", head->val ); head = head->next; } putchar( '\n' ); } // 删除链表 void del( node head ) { node tmp; while ( head ) { tmp = head; head = head->next; free( tmp ); } } #include <cmath> int main() { int n; n = scanf( "\n\n%d\n", &n ); printf("n=%d\n", n); int a[] = { 6,1,3,9,2,8,5,0,7,4 }; node head, pos; head = create( a, a + 10 ); print( head ); pos = find( head, 2 ); // 找到2的位置 insert( &head, pos, 999 ); // 在2后面插一个999 remove( &head, pos->next->next ); // 删除8 print( head ); del( head ); return 0; }