同步课 / 数据结构

#define MAX 255
typedef  char SString[MAX+1];
void InitStr(SString S)   
{    
   S[0] = 0;      
}   
void CreateStr(SString S, char chars[])    
{    
    int i;    
    for (i=0; chars[i]!='\0' && i+1<MAX; ++i)    
       S[i+1] = chars[i];    
   S[0] = i;           
} 
void replace(SString S,SString T,SString P)
{
    char *p;
    int i=0,j=1;
    int s,l,k;
    while (i<=S[0]&& j<=T[0])
    {
        if (S[i]==T[j])
        {
            ++i;
            ++j;
        }
        else
        {
            i=i-j+2;
            j=1;
        }
        if (j>T[0])
        {
            s=i-T[0];
        }/[找]到子串的位置s
    }
    if (T[0]==P[0])
    {
        for (l = 0; l < T[0]; l++)
        {
            S[s+l]=P[1+l];
        }
    }
    if (T[0]<P[0])
    {
        for ( k = 0; k <(P[0]-T[0]); k++)
        {
            for (p=&S[S[0]+1];p>=&S[s];--p)
             {
                 *(p+1)=*(p);
             }
           S[0]=S[0]+1;
        }
        for (l = 0; l <P[0]; l++)
        {
            S[s+l]=P[1+l];
        }
    }
}
int main (void)
{
    int i;
    SString S;
    SString T;
    SString P;
    InitStr(S);
    CreateStr( S,"abcabbreadyeafd");
    InitStr(T);
    CreateStr( T,"ready");
    InitStr(P);
    CreateStr( P,"replaceok");
    replace(S,T,P);
    for (i = 1; i <= S[0]; i++)
    {
        printf("%c",S[i]);
    }
}

以后作业不要提交没有格式的，老师实在是看着头大啊，看的对不上行了有很大可能给判错。下面第一个图片是不合格的，第二个是合格的格式，请同学们今后一定要提交注意。

/***
*DynaLnkList.cpp - 动态链表，即顺序表的动态链式存储实现
*
*
*题目：实验2-2 线性表的动态链式存储实现
*
*班级：软件3班
*
*姓名：陈立风

*
*学号：2015015298
*
****/

#include <stdlib.h>
#include <malloc.h>
#include <memory.h>
#include <assert.h>
#include "DynaLnkList.h"
#include<stdio.h>  //输入输出函数头文件
#include <string.h> //compare
#define LIST_INIT_SIZE 10  //定义最初申请的内存的大小
#define LIST_INCREMENT 2  //每一次申请内存不足的时候扩展的大小
#define OVERFLOW false  //异常抛出返回值
#define ERROR false  //异常抛出返回值
#define FALSE false  //异常抛出返回值
#define TRUE true  //程序正确执行抛出返回值 
#define INFEASIBLE false //异常抛出返回值
#define OK true  //程序正确执行抛出返回值 

typedef int ElemType;  //别名声明，其实int可以用任意的名字代入
typedef bool Status;  //别名声明

/*------------------------------------------------------------
操作目的： 初始化链表
初始条件： 无
操作结果： 构造一个空的线性表
函数参数：
LinkList *L 待初始化的线性表
返回值：
bool 操作是否成功
------------------------------------------------------------*/
bool InitList(LinkList *L)
{
    L=(LinkList)malloc(sizeof(LNode));
    if(!L)
    exix(OVERFLOW);
    L->next=NULL;
}

/*------------------------------------------------------------
操作目的： 销毁链表
初始条件： 线性表L已存在
操作结果： 销毁线性表L
函数参数：
LinkList *L 待销毁的线性表
返回值：
无
------------------------------------------------------------*/
void DestroyList(LinkList *L)
{    LinkList q;
while(L)
{
q=L->next;
free(L);
L=q;
}
L->next=NULL;
}

/*------------------------------------------------------------
操作目的： 判断链表是否为空
初始条件： 线性表L已存在
操作结果： 若L为空表，则返回true，否则返回false
函数参数：
LinkList L 待判断的线性表
返回值：
bool 是否为空
------------------------------------------------------------*/
bool ListEmpty(LinkList L)
{   if(L->next)
     return 0;
     else
     return 1;
}

/*------------------------------------------------------------
操作目的： 得到链表的长度
初始条件： 线性表L已存在
操作结果： 返回L中数据元素的个数
函数参数：       
LinkList L 线性表L
返回值：
int 数据元素的个数
------------------------------------------------------------*/
int ListLength(LinkList L)
{   int i=0;
    LinkList p=L->next;
    while(p)
    {
    i++;
    p=p->next;
    }
 
    return i;
}

/*------------------------------------------------------------
操作目的： 得到链表的第i个元素
初始条件： 线性表L已存在，1<=i<=ListLength(L)
操作结果： 用e返回L中第i个数据元素的值
函数参数：
LinkList L 线性表L
int i 数据元素的位置
ElemType *e 第i个数据元素的值
返回值：
bool 操作是否成功
------------------------------------------------------------*/
bool GetElem(LinkList L, int i, ElemType *e)
{
int j=1;
LinkList p=L->next;
while(p&&j<i)
{
p=p->next;
j++;
}
if(!p||j>i)
  return ERROR;
  e=p->data;
    return OK;
}

/*------------------------------------------------------------
操作目的： 得到链表指定元素的位置
初始条件： 线性表L已存在
操作结果： 返回L中第一个与e满足关系compare()的数据元素的位序。
若这样的元素不存在则返回0。
函数参数：
LinkList L 线性表L
ElemType e 数据元素e
int (*fp)() 用于比较相等的函数指针
返回值：
int 与e满足关系compare()的数据元素的位序
------------------------------------------------------------*/
int LocateElem(LinkList L, ElemType e, int (*fp)(ElemType, ElemType))
{
int i=0;
LinkList p=L->next;
while (p)
{
if(compare(p->data,e))
i++;
p=p->next;
}
if(i<ListLength(L))
return i;
else 
return 0;
}

/*------------------------------------------------------------
操作目的： 得到链表指定元素的前驱
初始条件： 线性表L已存在
操作结果： 若cur_e是L的数据元素，且不是第一个，则用pre_e返回
它的前驱，否则操作失败，pre_e无定义
函数参数：
LinkList L 线性表L
ElemType cur_e 数据元素cur_e
ElemType *pre_e 前驱数据元素
返回值：
bool 操作是否成功
------------------------------------------------------------*/
bool PriorElem(LinkList L, ElemType cur_e, ElemType *pre_e)
{
LinkList q,p=L->next;
while(p->next)
{
q=p->next;
if(q->data==cur_e)
{
pre_e=p->data;
return OK;
}
p=q;
}
    return INFEASIBLE;
}

/*------------------------------------------------------------
操作目的： 得到链表指定元素的后继
初始条件： 线性表L已存在
操作结果： 若cur_e是L的数据元素，且不是最后一个，则用nxt_e返
回它的后继，否则操作失败，nxt_e无定义
函数参数：
LinkList L 线性表L
ElemType cur_e 数据元素cur_e
ElemType *nxt_e 后继数据元素
返回值：
bool 操作是否成功
------------------------------------------------------------*/
bool NextElem(LinkList L, ElemType cur_e, ElemType *nxt_e)
{
LinkList p=L->next;
while(p->next)
{
if(p->data==cur_e)
{
next_e=p->next->data;
return OK;
}
p=p->next;
}
    return INFEASIBLE;
}

/*------------------------------------------------------------
操作目的： 遍历链表
初始条件： 线性表L已存在
操作结果： 依次对L的每个元素调用函数fp
函数参数：
LinkList L 线性表L
void (*fp)() 访问每个数据元素的函数指针
返回值：
无
------------------------------------------------------------*/
void ListTraverse(LinkList L, void (*fp)(ElemType))
{   LinkList p=L->next;
    while(p!=NULL)
    {
    vi(P->data);
    p=p->next;
    }
   printf("\n");
}

/*------------------------------------------------------------
操作目的： 清空链表
初始条件： 线性表L已存在
操作结果： 将L置为空表
函数参数：
LinkList L 线性表L
返回值：
无
------------------------------------------------------------*/
void ClearList(LinkList L)
{    LinkList q,p;
     p=L->next;
     while(p)
     {
      q=p->next;
      free(p);
      p=q;
     }
   L->next==NULL;
}

/*------------------------------------------------------------
操作目的： 在链表的指定位置插入结点，插入位置i表示在第i个
元素之前插入
初始条件： 线性表L已存在，1<=i<=ListLength(L) + 1
操作结果： 在L中第i个位置之前插入新的数据元素e，L的长度加1
函数参数：
LinkList L 线性表L
int i 插入位置
ElemType e 待插入的数据元素
返回值：
bool 操作是否成功
------------------------------------------------------------*/
bool ListInsert(LinkList L, int i, ElemType e)
{     int j=0;
      LinkList p=L;
      LinkList q;
      while(j<i-1)
      {
          p=p->next;
          j++;
      }
      q=(LinkList)malloc(sizeof(LNode));
      q->data=e;
      q->next=p->next;
      p->next=q;
    return 0;
}

/*------------------------------------------------------------
操作目的： 删除链表的第i个结点
初始条件： 线性表L已存在且非空，1<=i<=ListLength(L)
操作结果： 删除L的第i个数据元素，并用e返回其值，L的长度减1
函数参数：
LinkList L 线性表L
int i 删除位置
ElemType *e 被删除的数据元素值
返回值：
bool 操作是否成功
------------------------------------------------------------*/
bool ListDelete(LinkList L, int i, ElemType *e)
{int j=0;
LinkList p=L,q;
while(p->next&&j<i-1)  //寻找第i个结点，并令P指向其前驱
{
p=p->next;
j++;
}
if(!p->next||j>i-1)  //删除位置不合理
return ERROR;
q=p->next;  //删除并释放结点
p->next=q->next;
e=q->data;
free(q);
return OK;
}

 /***
*DynaSeqList.cpp - 动态顺序表，即顺序表的动态数组实现
*
*
*题目：实验2-1 线性表的动态顺序存储实现
*
*班级：5班
*
*姓名：刘向伟
*
*学号：2015015384
* 
****/

#include <stdlib.h>
#include <malloc.h>
#include <memory.h>
#include <assert.h>
#include "DynaSeqList.h"

const int LIST_INIT_SIZE = 100;	// 表初始分配的最大长度
const int LISTINCREMENT  = 10;	// 分配内存的增量

/*------------------------------------------------------------
操作目的：	初始化顺序表
初始条件：	无
操作结果：	构造一个空的线性表
函数参数：
SqList *L	待初始化的线性表
返回值：
bool	操作是否成功
------------------------------------------------------------*/
bool InitList(SqList *L)
{
L->elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(NULL==L->elem)return false;
L->length=0;
L->listsize=LIST_INIT_SIZE;
}

/*------------------------------------------------------------
操作目的：	销毁顺序表
初始条件：	线性表L已存在
操作结果：	销毁线性表L
函数参数：
SqList *L	待销毁的线性表
返回值：
无
------------------------------------------------------------*/
void DestroyList(SqList *L)
{
free(L->elem);
L->elem=NULL;
L->length=0;
L->listsize=0;
}

/*------------------------------------------------------------
操作目的：	判断顺序表是否为空
初始条件：	线性表L已存在
操作结果：	若L为空表，则返回true，否则返回false
函数参数：
SqList L	待判断的线性表
返回值：
bool	是否为空
------------------------------------------------------------*/
bool ListEmpty(SqList L)
{

if(L.length==0)
return true;
else
return false;
}

/*------------------------------------------------------------
操作目的：	得到顺序表的长度
初始条件：	线性表L已存在
操作结果：	返回L中数据元素的个数
函数参数：
SqList L	线性表L
返回值：
int	数据元素的个数
------------------------------------------------------------*/
int ListLength(SqList L)
{
return(L.length);
}

/*------------------------------------------------------------
操作目的：	得到顺序表的第i个元素
初始条件：	线性表L已存在，1<=i<=ListLength(L)
操作结果：	用e返回L中第i个数据元素的值
函数参数：
SqList L	线性表L
int i	数据元素的位置
ElemType *e	第i个数据元素的值
返回值：
bool	操作是否成功
------------------------------------------------------------*/
bool GetElem(SqList L, int i, ElemType *e)
{
if(i<1 || i>L.length)
return 0;
e=*(L.elem+i-1);
return 1;
}

/*------------------------------------------------------------
操作目的：	得到顺序表指定元素的位置
初始条件：	线性表L已存在
操作结果：	返回L中第一个与e满足关系compare()的数据元素的位序。
若这样的元素不存在则返回0。
函数参数：
SqList L	线性表L
ElemType e	数据元素e
int (*fp)()	用于比较相等的函数指针
返回值：
int	与e满足关系compare()的数据元素的位序
------------------------------------------------------------*/
int LocateElem(SqList L, ElemType e, int (*fp)(ElemType, ElemType))
{
int i=1;  //i的初始值为第一个元素的位序
ElemType *p=L.elem;//p的初始值为第一个元素的存储位置
while(i<=L.length &&!compare(*p++,e))//i未超出表的范围且未找到满足关系的数据元素
++i;//继续向后找
if(i<=L.length)/到满足关系的数据元素
return i;//返回其位序
else //未找到满足关系的数据元素
return 0;
}

/

邯郸—孟冰 2016/10/11 20:46:44
*------------------------------------------------------------
操作目的：	得到顺序表指定元素的前驱
初始条件：	线性表L已存在
操作结果：	若cur_e是L的数据元素，且不是第一个，则用pre_e返回
它的前驱，否则操作失败，pre_e无定义
函数参数：
SqList L	线性表L
ElemType cur_e	数据元素cur_e
ElemType *pre_e	前驱数据元素
返回值：
bool	操作是否成功
------------------------------------------------------------*/
bool PriorElem(SqList L, ElemType cur_e, ElemType *pre_e)
{
int i=2;//从第二个元素开始
ElemType *p=L.elem+1;//p指向第二个元素
while(i<=L.length && *p!=cur_e)//i未超出表的范围且未找到值为cur_e的元素
{
p++;//p指向下一个元素
i++;//i计数加1
}
if(i>L.length)//到表结束处还未找到值为cur_e的元素
return false;
else
{
pre_e=*--p;//p指向前一个元素（cur_e的前驱），将所指元素的值赋给pre_e
return true;
}
}

/*------------------------------------------------------------
操作目的：	得到顺序表指定元素的后继
初始条件：	线性表L已存在
操作结果：	若cur_e是L的数据元素，且不是最后一个，则用nxt_e返
回它的后继，否则操作失败，nxt_e无定义
函数参数：
SqList L	线性表L
ElemType cur_e	数据元素cur_e
ElemType *nxt_e	后继数据元素
返回值：
bool	操作是否成功
------------------------------------------------------------*/
bool NextElem(SqList L, ElemType cur_e, ElemType *nxt_e)
{
int i=1; // 从第1个元素开始
   ElemType *p=L.elem; // p指向第1个元素
   while(i<L.length&&*p!=cur_e) // i未到表尾且未找到值为cur_e的元素
   { p++; // p指向下一个元素
     i++; // 计数加1
   }
   if(i==L.length) // 到表尾的前一个元素还未找到值为cur_e的元素
     return false; // 操作失败
   else // 找到值为cur_e的元素，并由p指向其
   { nxt_e=*++p; // p指向下一个元素(cur_e的后继)，将所指元素的值赋给next _e
     return true; // 操作成功
   }
}

/*------------------------------------------------------------
操作目的：	遍历顺序表
初始条件：	线性表L已存在
操作结果：	依次对L的每个元素调用函数fp
函数参数：
SqList L	线性表L
void (*fp)()	访问每个数据元素的函数指针
返回值：
无
------------------------------------------------------------*/
void ListTraverse(SqList L, void (*fp)(ElemType))
{
for(int i=0;i<=L.length-1;i++)
(*fp)(L.elem[i]);
}

/*------------------------------------------------------------
操作目的：	清空顺序表
初始条件：	线性表L已存在
操作结果：	将L置为空表
函数参数：
SqList *L	线性表L
返回值：
无
------------------------------------------------------------*/
void ClearList(SqList *L)
{
L->length=0;
}

/

邯郸—孟冰 2016/10/11 20:46:48
*------------------------------------------------------------
操作目的：	在顺序表的指定位置插入结点，插入位置i表示在第i个
元素之前插入
初始条件：	线性表L已存在，1<=i<=ListLength(L) + 1
操作结果：	在L中第i个位置之前插入新的数据元素e，L的长度加1
函数参数：
SqList *L	线性表L
int i	插入位置
ElemType e	待插入的数据元素
返回值：
bool	操作是否成功
------------------------------------------------------------*/
bool ListInsert(SqList *L, int i, ElemType e)
{
//判断插入位置
//考虑追加内存问题
ElemType *newbase,*q,*p;
   if(i<1||i>L->length+1) // i值不合法
     return false;
   if(L->length==L->listsize) // 当前存储空间已满，增加分配，修改
   { newbase=(ElemType*)realloc(L->elem,(L->listsize+2)*sizeof(ElemType));
     if(!newbase) // 存储分配失败
       return 0;
     L->elem=newbase; // 新基址赋给L.elem
     L->listsize+=2; // 增加存储容量
   }
   q=L->elem+i-1; // q为插入位置
   for(p=L->elem+L->length-1;p>=q;--p) // 插入位置及之后的元素右移(由表尾元素开始移)
     *(p+1)=*p;
   *q=e; // 插入e
   ++L->length; // 表长增1
   return true;
 }


/*------------------------------------------------------------
操作目的：	删除顺序表的第i个结点
初始条件：	线性表L已存在且非空，1<=i<=ListLength(L)
操作结果：	删除L的第i个数据元素，并用e返回其值，L的长度减1
函数参数：
SqList *L	线性表L
int i	删除位置
ElemType *e	被删除的数据元素值
返回值：
bool	操作是否成功
------------------------------------------------------------*/
bool ListDelete(SqList *L, int i, ElemType *e)
{
ElemType *p, *q;
if (i<1 || i>L->length) 
return 0; 
p = &(L->elem[i-1]); 
e = *p; 
q = L->elem+L->length-1; 
for (++p; p<=q; ++p) 
*(p-1) = *p; 
--L->length; 
return 1;
}