最近去了几次招聘会，发现考数据结构和算法的题目还真不少，于是乎重拾数据结构与算法（就是清华的那本）这本书，我把几个常见的算法写到这里。^_^ ^_^ 作为备份吧！
反转单链表
其实原理很简单：因为是单链表，只有一个链域，所以要想反转（或者说倒序）那就得把所有链域到过来。
图画得有点那个，呵呵，理解就行。下面给出具体代码。
可在附件里下载，注释也有。
下载附件linkedList.h 链表节点的定义已经对链表进行操作的函数的声明
linkedList.c 链表实现文件
testLinkedList.c 测试链表文件
file: linkedList.h
/**
*filename: linkedList.h
*author: mushan
*/
#ifndef LINKED_LIST_H
#define LINKED_LIST_H
typedef int elemType;
struct Node
{
elemType info; /* 节点的数据信息 */
struct Node *link; /* 指向下一个节点 */
};
typedef struct linkedList
{
struct Node *head; /* 单链表头节点（头节点是为了插入和删除的方便，其中并不存储数据） */
struct Node *last; /* 单链表尾指针（仅仅是一个指针，指向最后一个节点，而并不生成尾节点） */
int count; /* 单链表节点个数（不包括头节点） */
}linkedList;
/* 初始化单链表
*
*前提：list不为空
*结果：生成一个带头节点(由head指向头节点)，且count=0的单链表list
*/
void init(linkedList *list);
/*销毁单链表
*
*前提：list不为空
*结果：释放所有由list动态申请的内存（包括头节点也要释放）
*/
void destroy(linkedList *list);
/*清空单链表
*
*前提：list已经初始化
*结果：释放由list动态申请的内存（不包括头节点）
*/
void clear(linkedList *list);
/*向单链表表头插入一个节点（插在头节点后面）
*
*前提：list己经初始化
*结果：将节点插在头节点后面
*/
void insertFirst(linkedList *list, elemType e);
/*向单链表表尾插入一个节点
*
*前提：list己经初始化
*结果：将节点插在尾部
*/
void insertLast(linkedList *list, elemType e);
/*反转单链表（即 单链表倒序）
*
*前提：list已经初始化
*结果：list里面节点的排列顺序将反转（倒序）
*/
void reverse(linkedList *list);
/*顺序遍历单链表
*
*前提：list已经初始化
*结果：顺序遍历单链表中的所以节点info(不包括头节点)
*说明：参数中的visit为遍历时要对节点进行操作的函数（确切的说是函数指针），如果只想打印节点info的值，
* 那自己写个简单的print函数即可，测试文件中有介绍
*/
void traversal(const linkedList *list, void (*visit)(elemType e) );
#endif
|
file: linkedList.c
/**
*filename: linkedList.c
*author: mushan
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "linkedList.h"
/* 初始化单链表
*
*前提：list不为空
*结果：生成一个带头节点(由head指向头节点)，且count=0的单链表list
*/
void init(linkedList *list)
{
struct Node *node = NULL;
/* 生成头节点 */
node = (struct Node *)malloc(sizeof(struct Node));
assert(node != NULL);
node->link = NULL;
list->head = node; /* 让head指向头节点 */
list->last = NULL;
return;
}
/*销毁单链表
*
*前提：list不为空
*结果：释放所有由list动态申请的内存（包括头节点也要释放）
*/
void destroy(linkedList *list)
{
struct Node *curr = list->head; /* 指向头节点 */
struct Node *next = NULL;
while(curr != NULL)
{
next = curr->link; /* 保存下一个节点的地址（位置） */
free(curr); /* 释放当前节点 */
curr = next; /* 指向（处理）下一个节点 */
}
list->head = NULL;
list->last = NULL;
list->count = 0;
return;
}
/*清空单链表
*
*前提：list已经初始化
*结果：释放由list动态申请的内存（不包括头节点）
*/
void clear(linkedList *list)
{
struct Node *curr = list->head->link; /* 指向第一个节点 */
struct Node *next = NULL;
while(curr != NULL)
{
next = curr->link; /* 保存下一个节点的地址（位置） */
free(curr); /* 释放当前节点 */
curr = next; /* 指向（处理）下一个节点 */
}
list->head->link = NULL;
list->last = NULL;
list->count = 0;
return;
}
/*向单链表表头插入一个节点（插在头节点后面）
*
*前提：list己经初始化
*结果：将节点插在头节点后面
*/
void insertFirst(linkedList *list, elemType e)
{
struct Node *node = NULL;
node = (struct Node *)malloc(sizeof(struct Node));
assert(node != NULL);
node->info = e;
if(list->last == NULL)
{
/* 第一次插入节点 */
list->last = node;
}
/* 因为是插在头节点后面，所以新插入节点的link应该指向原先头节点的下一个节点（这里说的下一个节点即原先链表的第一个节点） */
node->link = list->head->link;
/* 新节点成为第一个节点，让头节点指向他 */
list->head->link = node;
list->count++;
return;
}
/*向单链表表尾插入一个节点
*
*前提：list己经初始化
*结果：将节点插在尾部
*/
void insertLast(linkedList *list, elemType e)
{
struct Node *node = NULL;
node = (struct Node *)malloc(sizeof(struct Node));
assert(node != NULL);
node->info = e;
node->link = NULL;
if(list->last == NULL)
{
/* 第一次插入节点 */
list->last = node;
list->head->link = node;
}
else
{
/* 不是第一个插入节点，则需将新节点接在原先链表的尾部 */
list->last->link = node;
/* 更新尾指针，使其指向新生成的最后一个节点 */
list->last = node;
}
list->count++;
}
/*反转单链表（即 单链表倒序）
*
*前提：list已经初始化
*结果：list里面节点的排列顺序将反转（倒序）
*/
void reverse(linkedList *list)
{
struct Node *prev = list->head; /* 当前处理节点的前一个节点 */
struct Node *curr = list->head->link; /* 当前处理的节点，初始化为第一个节点 */
struct Node *next = NULL; /* 当前处理节点的下一个节点 */
if(curr == NULL || curr->link == NULL)
{
/* 如果单链表没有插入节点（即刚初始化）或者只插入了一个节点 ，则不需要倒序（因为倒序前后是一样的）*/
return;
}
/* 下面3行将头节点和尾指针更新，注意next没有特效含义，仅仅作为2个变量交换的中间变量，就像一个temp */
next = list->last; /* 保存最后一个节点的地址 */
list->last = list->head->link; /* 更新尾指针 */
list->head->link = next; /* 更新头指针 */
while(curr->link != NULL)
{
next = curr->link; /* 保存当前处理节点的下一节点的地址（位置） */
curr->link = prev; /* 反转当前节点的链域，让他指向前一个节点 */
prev = curr;
curr = next; /* 指针后移，处理下一节点 */
}
/* 上面的while循环不会处理最后一个节点，接下来处理最后一个节点，
如果在linkedList的定义中加设一个尾节点的话就不要处理这个细节了 */
curr->link = prev; /* while结束后curr已经指向最后一个节点了 */
/* 将反转后的最后一个节点（即反转前的第一个节点）的链域设置为NULL */
list->last->link = NULL;
return;
}
/*顺序遍历单链表
*
*前提：list已经初始化
*结果：打印出单链表中的所以节点info(不包括头节点)
*说明：参数中的visit为遍历时要对节点进行操作的函数（确切的说是函数指针），如果只想打印节点info的值，
* 那自己写个简单的print函数即可，测试文件中有介绍
*/
void traversal(const linkedList *list, void (*visit)(elemType e) )
{
struct Node *ptr = list->head->link;
while(ptr != NULL)
{
visit(ptr->info);
ptr = ptr->link;
}
return;
}
|
file:testLinkedList.c
/**
*filename: testLinkedList.c
*author: mushan
*/
#include <stdio.h>
#include <stdlib.h>
#include "linkedList.h"
/* 该函数是要传递给travers函数的参数 */
void printInt(elemType e);
int main(int argc, char *argv[])
{
linkedList list;
init(&list); /* 初始化 */
insertLast(&list, 1);
insertLast(&list, 10);
insertLast(&list, 15);
insertLast(&list, 54);
insertLast(&list, 23);
printf("linkedList element(s) are :\n[ ");
/* 遍历单链表，把printInt（其实就是一个指针而已）传给travers即可 */
traversal(&list, printInt);
printf("]\n");
reverse(&list);
printf("after reverse, linkedList element(s) are :\n[ ");
traversal(&list, printInt);
printf("]\n");
clear(&list);
printf("linkedList element(s) are :\n[ ");
traversal(&list, printInt);
printf("]\n");
return 0;
}
/******************************************************************
*因为我在linkedList.h文件中typedef int elemType，即elemType为int型，
*所以就直接用%d打印了 ，如果elemType不是int，请自己编写打印函数
*
*****************************************************************/
void printInt(elemType e)
{
printf("%d ", e);
}
|
三个文件的压缩档
 |
| 文件: | linkedList.zip |
| 大小: | 3KB |
| 下载: | 下载 |
|
阅读(8473) | 评论(0) | 转发(0) |
