赞
踩
void delx(SeqList *L,char x){
int i,j=0;
for(i=0;i<=L->last;i++){
if(L->data[i]!=x){
L->data[j]=L->data[i];
j++;
}
}
L->last=j-1;
}
法一:
void delxy(SeqList *L,char a,char b){
int i=0;
int j=0;
if(a>b){
printf("区间不合法!\n");
}else{
for(i=0;i<=L->last&&L->data[i]<a;i++);
if(i>L->last){ //不存在元素a
printf("不存在该元素!\n");
}
for(j=i;j<=L->last&&L->data[j]<=b;j++);
for(;j<=L->last;i++,j++){
L->data[i]=L->data[j];
}
}
L->last=i-1;
}
法二:
void delxy2(SeqList *L,char a,char b){
int i=0;
int k=0;
if(a>b){
printf("区间不合法!\n");
}else{
for(i=0;i<=L->last;i++){
if(L->data[i]>=a&&L->data[i]<=b)
k++;
else{ //当前元素往前移k个位置
L->data[i-k]=L->data[i];
}
}
}
L->last=L->last-k;
}
//逆置顺序表
void ReverseList(SeqList *L){
int i;
int j=(L->last)/2;
char temp;
for(i=0;i<=j;i++){
temp=L->data[i];
L->data[i]=L->data[L->last-i];
L->data[L->last-i]=temp;
}
}
void delsame(SeqList *L){
int i=0;
int j;
for(j=1;j<=L->last;j++){
if(L->data[i]!=L->data[j]){
L->data[i+1]=L->data[j];
i++;
}
}
L->last=i;
}
void mergeList(SeqList *LA,SeqList *LB,SeqList *LC){
int i=0;
int j=0;
int k=0;
printf("la的长度是:%d\n",LA->last);
printf("lb的长度是:%d\n",LB->last);
while(i<=LA->last && j<=LB->last)
if(LA->data[i]<=LB->data[j]){
LC->data[k]=LA->data[i];
i++;
k++;
}else{
LC->data[k]=LB->data[j];
j++;
k++;
}
while(i<=LA->last){ //表示LA没有遍历完 LB遍历完了
LC->data[k++]=LA->data[i++];
}
while(j<=LB->last){ //表示LB没有遍历完 LA遍历完了
LC->data[k++]=LB->data[j++];
}
LC->last=LA->last+LB->last;
}
/**
* 移动顺序表中的元素,将小于表头的元素放到前半部分,将大于表头的元素放到后半部分
*/
void move(SeqList *L) {
char head = L->data[0];
// 定义两根指针,分别指向顺序表中的第一个元素和最后一个元素
int i = 0;// 指针 i 从前往后移动
int j = L->last;// 指针 j 从后往前移动
// 当 i==j 时结束循环
while (i < j) {
// 从前往后移动,遇到第一个比你表头元素大的整数停止,注意 i<j 是必须的,因为指针 i 在不断增加过程中可能会大于 j 甚至超出顺序表的边界范围,导致出错
while (i < j && L->data[i] < head) {
// 如果遇到比表头元素小的整数,则 i 指针不断前进,直到遇到第一个比你表头元素大的整数停止
i++;
}
// 从后往前移动,遇到第一个比表头元素小的整数停止
while (i < j && L->data[j] > head) {
// 如果遇到比表头元素大的整数,则 j 指针不断前进,直到遇到第一个比你表头元素小的整数停止
j--;
}
// 当 i 遇到第一个比表头元素大的整数,j 遇到第一个比表头元素小的整数,则交换 i 和 j所表示的元素值
if (i < j) {
// 交换 data[i] 和 data[j] 的值
char temp = L->data[i];
L->data[i] = L->data[j];
L->data[j] = temp;
}
}
}
//单链表的就地逆置问题
void ReverseList(LinkList *L){
Node *p,*q;
LinkList link;
link = *L;
p=link->next;
link->next=NULL;
while(p!=NULL){
q=p->next;
//头插法
p->next=link->next;
link->next=p;
p=q;
}
}
//从尾到头输出元素
void RprintList(LinkList L){
if(L->next!=NULL){
RprintList(L->next);
}
if(L!=NULL){
printf("元素值为:%d\n",L->data);
}
}
//移动顺序表中小于和大于表头的元素
void changelist(LinkList *L){
Node *p,*q,*pre,*p1;
LinkList link;
link=*L;
pre=p1=link->next;
p=p1->next;
while(p!=NULL){
q=p->next;
if(p1->data<p->data){
//后移即可
pre=p;
p=q;
}else{
pre->next=p->next;
p->next=link->next;
link->next=p;
p=q;
}
}
}
//删除最大元素
void DelMax(LinkList *L){
Node *maxn;
Node *p,*pre,*premax;
LinkList link;
link = *L;
pre=premax=link;
p=maxn=link->next;
while(p!=NULL){
if(p->data>maxn->data){
maxn=p;
premax=pre;
}
pre=p;
p=p->next;
}
printf("最大值为:%d\n",maxn->data);
premax->next=maxn->next;
free(maxn);
}
//删除单链表中所有大于mink且小于maxk的元素(有序)
void delAtoB(LinkList *L,int mink,int maxk){
LinkList link;
link=*L;
Node *p,*q,*pre;
pre=link;
p=pre->next;
while(p->data<mink||p->data>maxk){
if(p->data!=x){//继续向后遍历
pre=p;
p=p->next;
}else{
q=p;
p=p->next;
pre->next=q->next;
free(q);
}
}
}
//删除单链表中所有值为x的结点
void delX(LinkList *L,int x){
LinkList link;
link=*L;
Node *p,*q,*pre;
pre=link;
p=pre->next;
while(p!=NULL){
if(p->data!=x){//继续向后遍历
pre=p;
p=p->next;
}else{
//相等,删除结点
q=p;
p=p->next;
pre->next=q->next;
free(q);
}
}
}
//删除单链表中所有值重复的元素
void delsame(LinkList *L){
Node *p,*q;
LinkList link;
link=*L;
p=link;
while(p->next!=NULL){
q=p->next;
if(p->data==q->data){
//删除q结点
p->next=q->next;
}else{
p=q;
}
}
}
# include<stdio.h>
#include <stdlib.h>
typedef struct Node{ //结点 定义单链表结点类型
int data; //数据域 每个节点存放一个数据元素
struct Node * next; //指针域 指针指向下一个节点
} Node,*LinkList;
//初始化一个单链表
int InitList(LinkList *L){
*L = (Node *)malloc(sizeof(Node)); //头结点
if(*L==NULL){
printf("申请空间失败\n");
return 0;
}
(*L)->next=NULL; //建立空的单链表L
return 1;
}
//判空
int EmptyList(LinkList *L){
if((*L)->next==NULL)
return 1;
else return 0;
}
//插入到指定结点p之后
int InsListX(Node *p,int e){
if(p==NULL){
return 0;
}
Node *s;
s=(Node *)malloc(sizeof(Node));
s->data=e;
s->next=p->next;
p->next=s;
return 1;
}
//按位序查找元素
Node * Get(LinkList L,int i){
if(i<0)
return NULL;
Node *p;
int j;
p=L;
j=0;
while(p!=NULL&& j<i){
p=p->next;
j++;
}
return p;
}
//按位序插入
int InsList(LinkList *L,int i,int e){
// Node *pre,*s;
// int k;
// int x=e;
// if(i<1){
// printf("插入的位置不合法!\n");
// return 0;
// }
// //从头结点开始 找第i-1个结点
// pre = *L;
// k=0;
// while(pre!=NULL && k<i-1) {
// pre = pre->next;
// k++;
// }
Node *pre;
int y = i-1;
LinkList link = *L;
pre = Get(link,y);
// if(pre==NULL){ //第i-1个结点不存在
// printf("插入的位置不合法!\n");
// return 0;
// }
// s=(Node *)malloc(sizeof(Node));
// s->data=e;
// s->next=pre->next;
// pre->next=s;
// return 1;
int x=e;
return InsListX(pre,x);
}
//在指定结点前插入:
int InsListBefore(Node *p,int e){
if(p==NULL){
return 0;
}
Node *s = (Node *)malloc(sizeof(Node));
s->next=p->next;
p->next=s;
s->data=p->data;
p->data=e;
return 1;
}
//按位序删除
int DelList(LinkList *L,int i,int *e){
Node *pre,*r;
int k;
if(i<1){
printf("删除的位置不合法!\n");
return 0;
}
//从头结点开始 找第i-1个结点
pre = *L;
k=0;
while(pre!=NULL && k<i-1) {
pre = pre->next;
k++;
}
if(pre==NULL){ //第i-1个结点不存在
printf("删除的位置不合法!\n");
return 0;
}
r=pre->next;
*e=r->data;
pre->next=r->next;
free(r);
return 1;
}
//删除指定结点:
int DelListX(Node *p){
if(p==NULL){
return 0;
}
Node *q = p->next;
p->data=q->data;
p->next=q->next;
free(q);
return 1;
}
//按值查找元素
Node * Locate(LinkList L,int key){
Node *p;
p=L->next;
while(p!=NULL){
if(key!=p->data){
p=p->next;
}else
break;
}
return p;
}
//尾插法建立单链表
void CreateFromTail(LinkList *L){
int flag=1;
Node *r,*s;
r=*L;
int c;
while(flag){
c=getchar();
getchar();
if(c!='$'){
s=(Node *)malloc(sizeof(Node));
s->data=c;
r->next=s;
r=s;
}else{
flag=0;
r->next=NULL;
}
}
}
//头插法建立单链表
void CreateFromHead(LinkList *L){
Node *s;
LinkList link;
int c;
int flag=1;
link=*L;
while(flag){
c=getchar();
getchar();
if(c!='$'){
s=(Node *)malloc(sizeof(Node));
s->data=c;
s->next=link->next;
link->next=s;
}else
flag=0;
}
}
//单链表的就地逆置问题
void ReverseList(LinkList *L){
Node *p,*q;
LinkList link;
link = *L;
p=link->next;
link->next=NULL;
while(p!=NULL){
q=p->next;
//头插法
p->next=link->next;
link->next=p;
p=q;
}
}
//求单链表长度
int ListLength(LinkList L){
printf("================求单链表长度=================\n");
Node *p;
p=L->next;
int j=0;
while(p!=NULL){
p=p->next;
j++;
}
return j;
}
//从尾到头输出元素
void RprintList(LinkList L){
if(L->next!=NULL){
RprintList(L->next);
}
if(L!=NULL){
printf("元素值为:%d\n",L->data);
}
}
//删除最大元素
void DelMax(LinkList *L){
Node *maxn;
Node *p,*pre,*premax;
LinkList link;
link = *L;
pre=premax=link;
p=maxn=link->next;
while(p!=NULL){
if(p->data>maxn->data){
maxn=p;
premax=pre;
}
pre=p;
p=p->next;
}
printf("最大值为:%d\n",maxn->data);
premax->next=maxn->next;
free(maxn);
}
//移动顺序表中小于和大于表头的元素
void changelist(LinkList *L){
Node *p,*q,*pre,*p1;
LinkList link;
link=*L;
pre=p1=link->next;
p=p1->next;
while(p!=NULL){
q=p->next;
if(p1->data<p->data){
//后移即可
pre=p;
p=q;
}else{
pre->next=p->next;
p->next=link->next;
link->next=p;
p=q;
}
}
}
//删除单链表中所有值为x的结点
void delX(LinkList *L,int x){
LinkList link;
link=*L;
Node *p,*q,*pre;
pre=link;
p=pre->next;
while(p!=NULL){
if(p->data!=x){//继续向后遍历
pre=p;
p=p->next;
}else{
//相等,删除结点
q=p;
p=p->next;
pre->next=q->next;
free(q);
}
}
}
//删除单链表中所有大于mink且小于maxk的元素(有序)
void delAtoB(LinkList *L,int mink,int maxk){
LinkList link;
link=*L;
Node *p,*q,*pre;
pre=link;
p=pre->next;
while(p!=NULL){
if(p->data<mink||p->data>maxk){//继续向后遍历
pre=p;
p=p->next;
}else{
q=p;
p=p->next;
pre->next=q->next;
free(q);
}
}
}
//删除单链表中所有值重复的元素
void delsame(LinkList *L){
Node *p,*q;
LinkList link;
link=*L;
p=link;
while(p->next!=NULL){
q=p->next;
if(p->data==q->data){
//删除q结点
p->next=q->next;
}else{
p=q;
}
}
}
int main(){
LinkList L; //声明一个指向单链表第一个结点的指针
if(InitList(&L)){
printf("初始化成功\n");
}
if(EmptyList(&L)){
printf("空单链表\n");
}
//插入操作
// printf("==============按位序插入数据==========\n");
// InsList(&L,1,8);
// InsList(&L,2,7);
// InsList(&L,3,6);
// InsList(&L,4,5);
// InsList(&L,5,4);
// InsList(&L,6,3);
//尾插法
printf("==============尾插法创建单链表==========\n");
CreateFromTail(&L);
// //头插法
// printf("==============头插法创建单链表==========\n");
// CreateFromHead(&L);
//
printf("此时单链表的长度为:%d\n",ListLength(L));
//按位序查找操作
printf("==============(未逆置前)位序查找数据==========\n");//封装程序 按位序插入 按位序删除
Node *p;
int res;
p = Get(L,4);
if(p!=NULL){
res = p->data;
printf("位序查找的数据为:%d\n",res);
}
// //删除操作
// printf("==============按位序删除数据==========\n");
// int x;
// if(DelList(&L,8,&x)){
// printf("删除的数据元素值为:%d\n",x);
// }
// printf("此时单链表的长度为:%d\n",ListLength(L));
// printf("==============单链表就地逆置==========\n");
// ReverseList(&L);
//按位序查找操作
// printf("==============(逆置后)位序查找数据==========\n");//封装程序 按位序插入 按位序删除
// Node *q;
// q = Get(L,4);
// if(q!=NULL){
// int res = q->data;
// printf("位序查找的数据为:%d",res);
// }
// printf("==============删除最大值==========\n");
// DelMax(&L);
// printf("==============删除相同值==========\n");
// delX(&L,98);
printf("==============删除所有相同值==========\n");
delsame(&L);
printf("==============从尾到头输出==========\n");
RprintList(L->next);
//
// //按值查找操作
// printf("==============按值查找数据==========\n");
// Node *q;
// q = Locate(L,8);
// if(q!=NULL){
// int res = q->data;
// printf("按值查找的数据为:%d",res);
// }
//
//
//
// if(EmptyList(&L)){
// printf("空单链表\n");
// }
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。