整数单链表的建立、查找、插入、删除、输出程序（线性表的链式存储实现），表中不允许有重复数据
#include<stdio.h>
#include<stdlib.h>
typedef struct node {
int data;
struct node* next;
} Node;
Node* create_list() {
Node* head = (Node*)malloc(sizeof(Node));
head->next = NULL;
return head;
}
Node* find_node(Node* head, int x) {
Node* p = head->next;
while (p != NULL) {
if (p->data == x) {
return p;
}
p = p->next;
}
return NULL;
}
void insert_node(Node* head, int x) {
if (find_node(head, x) != NULL) {
printf("重复的数据 %d\n", x);
return;
}
Node* p = (Node*)malloc(sizeof(Node));
p->data = x;
p->next = head->next;
head->next = p;
printf("成功插入数据 %d\n", x);
}
void delete_node(Node* head, int x) {
Node* prev = head;
Node* curr = head->next;
while (curr != NULL) {
if (curr->data == x) {
prev->next = curr->next;
free(curr);
printf("成功删除数据 %d\n", x);
return;
}
prev = curr;
curr = curr->next;
}
printf("没有数据 %d\n", x);
}
void print_list(Node* head) {
Node* p = head->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
void destroy_list(Node* head) {
Node* p = head;
while (p != NULL) {
Node* tmp = p->next;
free(p);
p = tmp;
}
}
int main() {
Node* head = create_list();
int choice, x;
do {
printf("1. 插入数据\n");
printf("2. 删除数据\n");
printf("3. 输出列表\n");
printf("0. 退出\n");
printf("请选择: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("请输入待插入数据：");
scanf("%d", &x);
insert_node(head, x);
break;
case 2:
printf("请输入待删除数据：");
scanf("%d", &x);
delete_node(head, x);
break;
case 3:
print_list(head);
break;
case 0:
break;
default:
printf("无效输入\n");
break;
}
printf("\n");
} while (choice != 0);
destroy_list(head);
return 0;
}
进行典型内部排序算法的比较，随机产生整数样本，进行四种排序，并比较各种排序算法的执行时间。
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#include "time.h"
#define MAXSIZE 20
typedef struct{
int key;
}RedType;
typedef struct{ //定义顺序表的存储结构
RedType *r; //存储空间基址，r[0]闲置或用作哨兵或用作缓冲区/
int length; //顺序表的长度
}SqList;
void InitSqList(SqList *L){
L->r=(RedType *)malloc((MAXSIZE+1)*sizeof(RedType));
L->length=0;
}//InitSqList
void CreateSqList(SqList *L){//输入数据元素个数，随机产生整数样本
int i;
srand((unsigned)time(0));
printf("\n请输入顺序表的长度: ");
scanf("%d",&L->length);
for ( i=1; i<=L->length; i++){
L->r[i].key=rand()%100;//随机产生整数样本
}
printf("\n\n未排序的数据为:\n");
for( i=1; i<=L->length; i++)
printf("%8d",L->r[i]);
}//CreateSqList
/*************************************直接插入排序********************************************/
void InsertSort(SqList *L){//直接插入排序
int i,j;
if(!L->length){
printf("该顺序表为空!");
}
for(i=2; i<=L->length; i++)
if(L->r[i].key < L->r[i-1].key){
L->r[0].key=L->r[i].key;//复制哨兵
for(j=i-1; L->r[0].key<L->r[j].key; j--){
L->r[j+1].key=L->r[j].key;//元素后移
}//for
L->r[j+1].key = L->r[0].key;//元素插入
}//if
}//InsertSort
/*************************************希尔排序********************************************/
void shellSort(SqList *L,int dk){//希尔排序
int i,j;
for(i=dk+1; i<=L->length; i++)
if(L->r[i].key < L->r[i-1].key){
L->r[0].key=L->r[i].key;//复制哨兵
for(j=i-dk; j>0&&L->r[0].key<L->r[j].key; j-=dk)
L->r[j+dk].key = L->r[j].key;//元素后移
L->r[j+dk].key = L->r[0].key;//元素插入
}//if
} //shellSort
void shellInsert(SqList *L){
int dk;
for(dk=L->length; dk>0; dk=dk/2){
shellSort(L,dk);//每次的增量都为dk/2,最终变为1
} //当dk变为1是就是最基本的直接插入排序
}//shellSqList
/*************************************快速排序********************************************/
int Partition(SqList *L, int low, int high){
int pivotkey;
L->r[0].key = L->r[low].key;
pivotkey = L->r[low].key;
while(low<high){
while(low<high && L->r[high].key >= pivotkey) --high;
L->r[low].key = L->r[high].key;
while(low<high && L->r[low].key <= pivotkey) ++low;
L->r[high].key = L->r[low].key;
}//while
//当low=high时跳出循环
L->r[low].key = L->r[0].key;
return low;
}//Partition
void QSort(SqList *L, int low, int high){//递归快速排序
int pivotloc;
if(low<high){
pivotloc = Partition(L, low, high);
QSort(L, low, pivotloc-1);
QSort(L, pivotloc+1, high);
}
}//QSort
/*************************************堆排序********************************************/
void HeapAdjust(SqList *L, int s, int m){
int j,rc;
rc = L->r[s].key;
for(j=2*s; j<=m; j*=2){
if(j<m && L->r[j].key < L->r[j+1].key) ++j;
if(rc > L->r[j].key) break;
L->r[s].key = L->r[j].key;
s = j;
}
L->r[s].key = rc;
}//HeapAdjust
void HeapSort(SqList *L){
int i,temp;
for (i=L->length/2; i>0; i--)
HeapAdjust(L,i,L->length);
for (i=L->length; i>1; i--){
temp = L->r[1].key;
L->r[1].key = L->r[i].key;
L->r[i].key = temp;
HeapAdjust(L,1,i-1);
}
}//HeapSort
/*************************************输出函数********************************************/
void outputSqList(SqList *L){//输出排序之后的元素
int i;
printf("\n该顺序表的长度为：:%d\n",L->length);
printf("\n\n排序了的数据为 : \n");
for(i=1; i<=L->length; i++){
printf("%8d",L->r[i].key);
}
printf("\n");
}//outputSqList
/*************************************复制链表函数********************************************/
void CopySqList(SqList *L, SqList *L_COPY){
int i;
if ( !L->length ){
printf("该顺序表为空！\n");
}
else{
for (i=1; i<=L->length; i++)
L_COPY->r[i].key = L->r[i].key;
L_COPY->length = L->length;
}
}//CopySqList
int main(){
SqList L, L_COPY;//L为初始顺序表 ,L_COPY为L的副本，用于排序
clock_t start,finish;
int select,flag;//用户输入的选项
flag = 1;
InitSqList(&L);
InitSqList(&L_COPY);
CreateSqList(&L);
while(flag){
//mnum=0;cnum=0;
CopySqList(&L,&L_COPY);
printf("\n请输入选:\n1. 直接插入排序\n2. 希尔排序\n3. 快速排序\n4. 堆排序\n5.退出\n");
scanf("%d",&select);
switch(select){
case 1:
start=clock();
InsertSort(&L_COPY);
finish=clock();
break;
case 2:
start=clock();
shellInsert(&L_COPY);
finish=clock();
break;
case 3:
start=clock();
QSort(&L_COPY,1,L.length);
finish=clock();
break;
case 4:
start=clock();
HeapSort(&L_COPY);
finish=clock();
break;
case 5:
flag=0;
exit(0);
}
outputSqList(&L_COPY);
//printf("\n排序花的时间 : %lf Seconds\n",double(finish-start));
}
return 0;
}
最后对，这些排序算法的复杂度进行一下简单的比较
| 算法种类 | 时间复杂度 | 空间复杂度 | 是否稳定 | ||
| 最好情况 | 平均情况 | 最坏情况 | |||
| 直接插入排序 | O(n) | O(n²) | O(n²) | O(1) | 是 |
| 希尔排序 | O(1) | 否 | |||
| 快速排序 | O(nlog₂n) | O(nlog₂n) | O(n²) | O(log₂n) | 否 |
| 堆排序 | O(nlog₂n) | O(nlog₂n) | O(nlog₂n) | O(1) | 否 |
# 优化前，按位序插入的单链表
#include <iostream>
using namespace std;
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
void ListInsert(LinkList &L, int i, ElemType e){
LNode *p=L, *s;
int j=0;
while(p && j<i-1){ // 找到位置i-1对应的结点p
p = p->next; ++j;
}
if(!p || j>i-1) return; // i值不合法（超出表长+1）
s = (LinkList)malloc(sizeof(LNode)); // 为新结点分配空间
s->data = e; // 将输入元素e赋值给新结点s的数据域
s->next = p->next; // 将结点s插入到结点p之后
p->next = s;
}
int main()
{
LinkList L=(LinkList)malloc(sizeof(LNode)); // 创建一个空链表,一个头指针
L->next = NULL;
ListInsert(L, 1, 10);
ListInsert(L, 2, 20);
}
# 优化后，使用尾插法建立单链表
#include <iostream>
using namespace std;
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
void ListInsert(LinkList &L, int i, ElemType e){
LNode *p=L, *s;
int j=0;
while(p && j<i-1){ // 找到位置i-1对应的结点p
p = p->next; ++j;
}
if(!p || j>i-1) return; // i值不合法（超出表长+1）
s = (LinkList)malloc(sizeof(LNode)); // 为新结点分配空间
s->data = e; // 将输入元素e赋值给新结点s的数据域
s->next = p->next; // 将结点s插入到结点p之后
p->next = s;
}
LinkList List_TailInsert(LinkList &L){
L = (LinkList)malloc(sizeof(LNode)); //创建头结点
LNode *s, *r = L; // r为表尾指针
ElemType x; // 设elemType为整型,用输入流输入元素
cin >> x;
while(x != 9999){ // 输入9999表示结束
// 在最后一个结点r后面插入新结点s
s = (LNode *)malloc(sizeof(LNode));
s->data = x; // 新建结点值
r->next = s; // 将新建点挂接到表尾
r = s; // r指向新的表尾结点
cin >> x; // 输入流二连
}
r->next = NULL; // 尾结点指针置空
return L; // 返回头结点地址
}
void ListPrint(LinkList L){
LNode* s = L->next;
while(s != NULL){
cout << s->data << ' ';
s = s->next;
}
}
int main(){
LinkList L; // 声明一个空双向链表
L = List_TailInsert(L); // 使用尾插法，正向建立单向链表
ListPrint(L); // 从第1个结点遍历输出单向链表所有元素
cout << endl;
return 0;
}