按位查找
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode { //定义单链表结构
int data; //每个节点存放一个数据
struct LNode *next; //指针指向下一个节点
}LNode, *LinkList;
bool InitList(LinkList &L);
bool Empty(LinkList L);
bool ListInsert(LinkList &L, int i, int e);
bool ListDelete(LinkList &L, int i, int &e);
LNode* GetElem(LinkList L, int i);
int main(void) {
LinkList L;
InitList(L);
if (Empty(L)) {
printf("链表为空!\n");
}
ListInsert(L, 1, 11);
ListInsert(L, 2, 22);
ListInsert(L, 3, 33);
ListInsert(L, 4, 44);
ListInsert(L, 5, 55);
ListInsert(L, 6, 66);
ListInsert(L, 7, 77);
ListInsert(L, 8, 88);
if (!Empty(L)) {
printf("插入成功!\n");
}
int e = 0;
ListDelete(L, 8, e);
//判断是否删除成功
LNode* node = NULL;
node = GetElem(L, 8);
if (node == NULL) {
printf("删除成功!\n");
}
node = GetElem(L, 6);
printf("获取元素:%d\n", node->data);
return 0;
}
//初始化空的单链表
bool InitList(LinkList &L) {
L = (LNode *)malloc(sizeof(LNode)); //分配头结点
if (L == NULL) { //内存不足,分配失败
return false;
}
L->next = NULL; //头结点之后暂时没有节点
return true;
}
//判断单链表是否为空(带头结点)
bool Empty(LinkList L) {
if (L->next == NULL) {
return true;
} else {
return false;
}
}
//在第i个位置插入元素e(带头结点)
bool ListInsert(LinkList &L, int i, int e) {
if (i < 1) {
return false;
printf("插入失败!\n");
}
LNode *p; //指针p指向当前扫描到的节点
int j = 0; //当前p指向的是第几个节点
p = L; //L指向头结点,头结点是第0个节点(不存数据)
while (p != NULL && j < i-1) { //循环找到第i-1个节点
p = p->next;
j++;
}
if (p == NULL) { //i值不合法
return false;
printf("插入失败!\n");
}
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s; //将节点s连接到p之后
return true; //插入成功
}
//按位序删除:带头结点
bool ListDelete(LinkList &L, int i, int &e) {
if (i < 1) {
return false;
}
LNode *p; //指针p指向当前扫描到的节点
int j = 0; //当前p指向的是第几个节点
p = L; //L指向头结点,头结点是第0个节点(不存数据)
while(p != NULL && j < i-1) { //循环找到第i-1个节点
p = p->next;
j++;
}
if (p==NULL) { //i值不合法
return false;
}
if (p->next == NULL) { //第i-1个节点之后已无其他节点
return false;
}
LNode *q = p->next; //令p指向被删除节点
e = q->data; //用e返回元素的值
p->next = q->next; //将*q节点从链中“断开”
free(q);
return true;
}
//按位查找,返回第i个元素(带头结点)
LNode* GetElem(LinkList L, int i) {
if (i < 0) {
return NULL;
}
LNode *p; //指针p指向当前扫描到的节点
int j = 0; //当前p指向的是第几个节点
p = L; //L指向头结点,头结点是第0个节点(不存数据)
while (p!=NULL && j<i) { //循环找到第i个节点
p = p->next;
j++;
}
return p;
}
封装之后
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode { //定义单链表结构
int data; //每个节点存放一个数据
struct LNode *next; //指针指向下一个节点
}LNode, *LinkList;
bool InitList(LinkList &L);
bool Empty(LinkList L);
bool ListInsert(LinkList &L, int i, int e);
bool ListDelete(LinkList &L, int i, int &e);
bool InsertNextNode(LNode *p, int e);
LNode* GetElem(LinkList L, int i);
int main(void) {
LinkList L;
InitList(L);
if (Empty(L)) {
printf("链表为空!\n");
}
ListInsert(L, 1, 11);
ListInsert(L, 2, 22);
ListInsert(L, 3, 33);
ListInsert(L, 4, 44);
ListInsert(L, 5, 55);
ListInsert(L, 6, 66);
ListInsert(L, 7, 77);
ListInsert(L, 8, 88);
if (!Empty(L)) {
printf("插入成功!\n");
}
int e = 0;
ListDelete(L, 8, e);
//判断是否删除成功
LNode* node = NULL;
node = GetElem(L, 8);
if (node == NULL) {
printf("删除成功!\n");
}
node = GetElem(L, 6);
printf("获取元素:%d\n", node->data);
return 0;
}
//初始化空的单链表
bool InitList(LinkList &L) {
L = (LNode *)malloc(sizeof(LNode)); //分配头结点
if (L == NULL) { //内存不足,分配失败
return false;
}
L->next = NULL; //头结点之后暂时没有节点
return true;
}
//判断单链表是否为空(带头结点)
bool Empty(LinkList L) {
if (L->next == NULL) {
return true;
} else {
return false;
}
}
//在第i个位置插入元素e(带头结点)
bool ListInsert(LinkList &L, int i, int e) {
if (i < 1) {
return false;
}
LNode *p = GetElem(L, i-1); //找到第i-1个节点
return InsertNextNode(p, e); //p后插入新元素e
}
//按位序删除:带头结点
bool ListDelete(LinkList &L, int i, int &e) {
if (i < 1) {
return false;
}
LNode *p = GetElem(L, i-1); //找到第i-1个节点
if (p==NULL) { //i值不合法
return false;
}
if (p->next == NULL) { //第i-1个节点之后已无其他节点
return false;
}
LNode *q = p->next; //令p指向被删除节点
e = q->data; //用e返回元素的值
p->next = q->next; //将*q节点从链中“断开”
free(q);
return true;
}
//按位查找,返回第i个元素(带头结点)
LNode* GetElem(LinkList L, int i) {
if (i < 0) {
return NULL;
}
LNode *p; //指针p指向当前扫描到的节点
int j = 0; //当前p指向的是第几个节点
p = L; //L指向头结点,头结点是第0个节点(不存数据)
while (p!=NULL && j<i) { //循环找到第i个节点
p = p->next;
j++;
}
return p;
}
//后插操作:在p节点之后插入元素e
bool InsertNextNode(LNode *p, int e) {
if (p == NULL) {
return false;
}
LNode *s = (LNode *)malloc(sizeof(LNode));
if (s == NULL) { //内存分配失败
return false;
}
s->data = e; //用节点s保存数据元素e
s->next = p->next;
p->next = s;
return true;
}
按值查找
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode { //定义单链表结构
int data; //每个节点存放一个数据
struct LNode *next; //指针指向下一个节点
}LNode, *LinkList;
bool InitList(LinkList &L);
bool Empty(LinkList L);
bool ListInsert(LinkList &L, int i, int e);
bool ListDelete(LinkList &L, int i, int &e);
bool InsertNextNode(LNode *p, int e);
LNode* LocalElem(LinkList L, int e);
LNode* GetElem(LinkList L, int i);
int main(void) {
LinkList L;
InitList(L);
if (Empty(L)) {
printf("链表为空!\n");
}
ListInsert(L, 1, 11);
ListInsert(L, 2, 22);
ListInsert(L, 3, 33);
ListInsert(L, 4, 44);
ListInsert(L, 5, 55);
ListInsert(L, 6, 66);
ListInsert(L, 7, 77);
ListInsert(L, 8, 88);
if (!Empty(L)) {
printf("插入成功!\n");
}
int e = 0;
ListDelete(L, 8, e);
//判断是否删除成功
LNode* node = NULL;
node = LocalElem(L, 88);
if (node == NULL) {
printf("删除成功!\n");
}
node = LocalElem(L, 66);
printf("获取元素位序:%d\n", node->data);
return 0;
}
//初始化空的单链表
bool InitList(LinkList &L) {
L = (LNode *)malloc(sizeof(LNode)); //分配头结点
if (L == NULL) { //内存不足,分配失败
return false;
}
L->next = NULL; //头结点之后暂时没有节点
return true;
}
//判断单链表是否为空(带头结点)
bool Empty(LinkList L) {
if (L->next == NULL) {
return true;
} else {
return false;
}
}
//在第i个位置插入元素e(带头结点)
bool ListInsert(LinkList &L, int i, int e) {
if (i < 1) {
return false;
}
LNode *p = GetElem(L, i-1); //找到第i-1个节点
return InsertNextNode(p, e); //p后插入新元素e
}
//按位序删除:带头结点
bool ListDelete(LinkList &L, int i, int &e) {
if (i < 1) {
return false;
}
LNode *p = GetElem(L, i-1); //找到第i-1个节点
if (p==NULL) { //i值不合法
return false;
}
if (p->next == NULL) { //第i-1个节点之后已无其他节点
return false;
}
LNode *q = p->next; //令p指向被删除节点
e = q->data; //用e返回元素的值
p->next = q->next; //将*q节点从链中“断开”
free(q);
return true;
}
//按值查找,找到数据域==e的节点
LNode* LocalElem(LinkList L, int e) {
LNode *p = L->next;
//从第一个节点开始查找数据域为e的节点
while (p != NULL && p->data != e) {
p = p->next;
}
return p;
}
//按位查找,返回第i个元素(带头结点)
LNode* GetElem(LinkList L, int i) {
if (i < 0) {
return NULL;
}
LNode *p; //指针p指向当前扫描到的节点
int j = 0; //当前p指向的是第几个节点
p = L; //L指向头结点,头结点是第0个节点(不存数据)
while (p!=NULL && j<i) { //循环找到第i个节点
p = p->next;
j++;
}
return p;
}
//后插操作:在p节点之后插入元素e
bool InsertNextNode(LNode *p, int e) {
if (p == NULL) {
return false;
}
LNode *s = (LNode *)malloc(sizeof(LNode));
if (s == NULL) { //内存分配失败
return false;
}
s->data = e; //用节点s保存数据元素e
s->next = p->next;
p->next = s;
return true;
}
求表长度
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode { //定义单链表结构
int data; //每个节点存放一个数据
struct LNode *next; //指针指向下一个节点
}LNode, *LinkList;
bool InitList(LinkList &L);
bool Empty(LinkList L);
bool ListInsert(LinkList &L, int i, int e);
bool InsertNextNode(LNode *p, int e);
LNode* GetElem(LinkList L, int i);
int length(LinkList L);
int main(void) {
LinkList L;
InitList(L);
if (Empty(L)) {
printf("链表为空!\n");
}
ListInsert(L, 1, 11);
ListInsert(L, 2, 22);
ListInsert(L, 3, 33);
ListInsert(L, 4, 44);
ListInsert(L, 5, 55);
ListInsert(L, 6, 66);
ListInsert(L, 7, 77);
ListInsert(L, 8, 88);
printf("链表长度为:%d\n",length(L));
return 0;
}
//初始化空的单链表
bool InitList(LinkList &L) {
L = (LNode *)malloc(sizeof(LNode)); //分配头结点
if (L == NULL) { //内存不足,分配失败
return false;
}
L->next = NULL; //头结点之后暂时没有节点
return true;
}
//判断单链表是否为空(带头结点)
bool Empty(LinkList L) {
if (L->next == NULL) {
return true;
} else {
return false;
}
}
//在第i个位置插入元素e(带头结点)
bool ListInsert(LinkList &L, int i, int e) {
if (i < 1) {
return false;
}
LNode *p = GetElem(L, i-1); //找到第i-1个节点
return InsertNextNode(p, e); //p后插入新元素e
}
//按位查找,返回第i个元素(带头结点)
LNode* GetElem(LinkList L, int i) {
if (i < 0) {
return NULL;
}
LNode *p; //指针p指向当前扫描到的节点
int j = 0; //当前p指向的是第几个节点
p = L; //L指向头结点,头结点是第0个节点(不存数据)
while (p!=NULL && j<i) { //循环找到第i个节点
p = p->next;
j++;
}
return p;
}
//后插操作:在p节点之后插入元素e
bool InsertNextNode(LNode *p, int e) {
if (p == NULL) {
return false;
}
LNode *s = (LNode *)malloc(sizeof(LNode));
if (s == NULL) { //内存分配失败
return false;
}
s->data = e; //用节点s保存数据元素e
s->next = p->next;
p->next = s;
return true;
}
//求表长度
int length(LinkList L) {
int len = 0; //统计表长
LNode *p = L;
while (p->next != NULL) {
p = p->next;
len++;
}
return len;
}